Why Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Go?

The Big Idea

Discover how tiny switches inside numbers can unlock huge power in your code!

The Scenario

Imagine you want to quickly check or change tiny parts of a number, like flipping a single light switch in a huge control panel. Doing this by hand, one by one, is slow and confusing.

The Problem

Manually converting numbers to binary, changing bits, and converting back is slow and full of mistakes. It's like trying to find one word in a huge book without an index.

The Solution

Bit manipulation lets you use simple commands to flip, check, or move bits directly inside numbers. It's like having a magic remote control that changes only the lights you want instantly.

Before vs After

✗ Before

num := 12 // binary 1100
// To flip 2nd bit manually:
num = 8 + 4 // manually calculate new value

✓ After

num := 12 // binary 1100
num = num ^ (1 << 2) // flip 3rd bit using XOR and shift

What It Enables

Bit manipulation enables lightning-fast control over data at the smallest level, making programs efficient and powerful.

Real Life Example

In video games, bit manipulation quickly checks which keys are pressed or which game features are active without slowing down the game.

Key Takeaways

Manual bit changes are slow and error-prone.

Bit manipulation uses simple operations to change bits fast.

This skill is key for efficient, low-level programming.

Practice

1. What is the result of the bitwise AND operation between 6 and 3? (6 = 110 in binary, 3 = 011 in binary)

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Convert numbers to binary

   6 in binary is 110, 3 in binary is 011.

2. Step 2: Perform bitwise AND

   110 AND 011 = 010 in binary, which is 2 in decimal.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   6 & 3 = 2 [OK]

Hint: AND keeps bits set in both numbers only [OK]

Common Mistakes:

• Confusing AND with OR operation
• Not converting numbers to binary before operation
• Mixing decimal and binary values

2. Which of the following is the correct syntax in Go to perform a bitwise XOR between variables a and b?

easy

A. c := a & b

B. c := a && b

C. c := a ^ b

D. c := a | b

Solution

1. Step 1: Recall Go bitwise operators

   In Go, '^' is the bitwise XOR operator.

2. Step 2: Match syntax

   c := a ^ b uses '^' correctly for XOR. Other options use logical AND (&&), OR (|), and AND (&).

3. Final Answer:

   c := a ^ b -> Option C

4. Quick Check:

   Bitwise XOR uses '^' in Go [OK]

Hint: XOR operator in Go is '^' symbol [OK]

Common Mistakes:

• Using '&&' which is logical AND, not bitwise
• Confusing OR '|' with XOR '^'
• Using '&' which is bitwise AND, not XOR

3. What is the output of the following Go code?

package main
import "fmt"
func main() {
  var x uint8 = 12  // binary 00001100
  var y uint8 = 5   // binary 00000101
  fmt.Println(x | y)
  fmt.Println(x & y)
  fmt.Println(x ^ y)
}

medium

A. 15
4
9

B. 14
4
9

C. 15
5
8

D. 13
4
9

Solution

1. Step 1: Convert x and y to binary

   x = 12 = 00001100, y = 5 = 00000101.

2. Step 2: Calculate bitwise OR, AND, XOR

   OR: 00001100 | 00000101 = 00001101 (13 decimal)
   AND: 00001100 & 00000101 = 00000100 (4 decimal)
   XOR: 00001100 ^ 00000101 = 00001001 (9 decimal)

3. Step 3: Verify output

   Output lines are:
   13
   4
   9

4. Final Answer:

   13 4 9 -> Option D

5. Quick Check:

   Bitwise OR, AND, XOR results match 13, 4, 9 [OK]

Hint: OR sets bits from either number, AND only common bits [OK]

Common Mistakes:

• Mixing up OR and XOR results
• Incorrect binary conversion
• Confusing decimal output values

4. The following Go code is intended to left shift the number 3 by 2 bits. Identify the error.

package main
import "fmt"
func main() {
  var a int = 3
  var b int = 2
  var c int = a << b
  fmt.Println(c)
}

medium

A. Error: shift count must be unsigned integer

B. No error, output is 12

C. Error: cannot shift int by int

D. Error: missing parentheses around shift

Solution

1. Step 1: Understand Go shift rules

   In Go, shift count must be unsigned integer or untyped constant. Here, b is int but allowed.

2. Step 2: Calculate left shift

   3 << 2 means shifting bits of 3 (00000011) left by 2 bits: 00001100 = 12 decimal.

3. Final Answer:

   No error, output is 12 -> Option B

4. Quick Check:

   3 << 2 = 12 [OK]

Hint: Shift count can be int variable in Go if within range [OK]

Common Mistakes:

• Assuming shift count must be uint explicitly
• Thinking parentheses are required around shift
• Confusing shift operators with arithmetic operators

5. Given a 8-bit unsigned integer n, write a Go expression using bitwise operators to toggle (flip) the 3rd bit (counting from 0, right to left) of n. Which expression correctly does this?

hard

A. n ^ (1 << 3)

B. n & (1 << 3)

C. n | (1 << 3)

D. ~n & (1 << 3)

Solution

1. Step 1: Understand toggling a bit

   Toggling means flipping the bit: if 0 becomes 1, if 1 becomes 0.

2. Step 2: Use XOR to toggle

   XOR with 1 flips the bit, XOR with 0 keeps it same. So, n ^ (1 << 3) flips the 3rd bit.

3. Step 3: Check other options

   AND keeps bit only if both are 1 (no toggle), OR sets bit to 1 (no toggle), NOT and AND combination does not toggle.

4. Final Answer:

   n ^ (1 << 3) -> Option A

5. Quick Check:

   XOR with mask toggles bit [OK]

Hint: XOR with 1 flips bit, XOR with 0 keeps bit same [OK]

Common Mistakes:

• Using AND or OR which don't toggle bits
• Confusing NOT operator usage
• Incorrect bit position shift