Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Go - Execution Trace

Concept Flow - Bit Manipulation Basics AND OR XOR NOT Left Right Shift

Start with two numbers

↓

Choose bit operation

↓

Apply bitwise op on bits

↓

Get result number

↓

End

Start with two numbers, pick a bit operation (AND, OR, XOR, NOT, SHIFT), apply it bit by bit, and get the result.

Execution Sample

DSA Go

a := 6  // 0110 in binary
b := 11 // 1011 in binary
c := a & b
fmt.Println(c)

This code does bitwise AND on 6 and 11, then prints the result.

Execution Table

Step	Operation	Bit Position	a bit	b bit	Result bit	Result (decimal)
1	AND	3 (8's place)	0	1	0	0
2	AND	2 (4's place)	1	0	0	0
3	AND	1 (2's place)	1	1	1	2
4	AND	0 (1's place)	0	1	0	2
5	Final Result	-	-	-	-	2

💡 All bits processed, final result is 2

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
a (decimal)	6	6	6	6	6	6
a (binary)	0110	0110	0110	0110	0110	0110
b (decimal)	11	11	11	11	11	11
b (binary)	1011	1011	1011	1011	1011	1011
Result (binary)	0000	0000	0000	0010	0010	0010
Result (decimal)	0	0	0	2	2	2

Key Moments - 3 Insights

Why does the AND operation result in 2 instead of a larger number?

Because AND only sets bits to 1 where both bits are 1. From the execution_table rows 1-4, only the 2's place bit is 1 in both numbers, so result bit is 1 only there.

Why do we check bits from highest to lowest position?

Checking from highest bit (3) to lowest (0) helps visualize how each bit contributes to the final number, as shown in execution_table steps 1 to 4.

What happens if we apply NOT to a number?

NOT flips every bit: 0 becomes 1, 1 becomes 0. This is different from AND/OR/XOR which combine two numbers, NOT works on one number alone.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result bit at bit position 1 during the AND operation?

A 0

B 1

C Undefined

D Same as a bit

💡 Hint

Check row 3 in execution_table under 'Result bit'

At which step does the result decimal value become 2?

A Step 3

B Step 2

C Step 4

D Step 1

💡 Hint

Look at 'Result (decimal)' column in execution_table rows

If we change b to 14 (1110 in binary), what would be the result of a & b at bit position 0?

A 1

B Same as a bit

C 0

D Same as b bit

💡 Hint

Bit position 0 of b=14 is 0, so AND with a bit 0 results in 0

Concept Snapshot

Bitwise operations work on bits of numbers.
AND: 1&1=1 else 0
OR: 1|0=1 else 0
XOR: 1^0=1 else 0
NOT: flips bits
SHIFT: moves bits left/right
Use to manipulate bits directly.

Full Transcript

Bit manipulation means working with the bits inside numbers. We start with two numbers and pick an operation like AND, OR, XOR, NOT, or SHIFT. Each operation looks at bits one by one. For example, AND sets a bit to 1 only if both bits are 1. We showed how 6 AND 11 works by checking each bit from highest to lowest. Only the bit in the 2's place is 1 in both, so the result is 2. NOT flips bits of one number. SHIFT moves bits left or right, changing the number. These operations help control data at the smallest level.

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