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

Mental Model

Bit manipulation changes numbers by working directly on their 0s and 1s. It uses simple rules to combine or flip bits quickly.

Analogy: Imagine a row of light switches (bits) that can be ON (1) or OFF (0). Bit operations are like flipping, combining, or shifting these switches to get new patterns.

Number: 13
Bits:  0 0 0 0 1 1 0 1
Index: 7 6 5 4 3 2 1 0

Dry Run Walkthrough

Input: Numbers: a=13 (00001101), b=10 (00001010)

Goal: Show how AND, OR, XOR, NOT, Left Shift, and Right Shift change bits of a and b

Step 1: Calculate a AND b

a: 00001101
b: 00001010
AND: 00001000 (8)

Why: AND keeps bits ON only if both a and b have 1 in that position

Step 2: Calculate a OR b

a: 00001101
b: 00001010
OR:  00001111 (15)

Why: OR turns bits ON if either a or b has 1 in that position

Step 3: Calculate a XOR b

a: 00001101
b: 00001010
XOR: 00000111 (7)

Why: XOR turns bits ON only if a and b differ in that position

Step 4: Calculate NOT a (invert bits)

a:  00001101
NOT: 11110010 (in 8-bit two's complement: -14)

Why: NOT flips every bit from 0 to 1 or 1 to 0

Step 5: Left shift a by 1 (a << 1)

a: 00001101
Left shift: 00011010 (26)

Why: Left shift moves bits left, adding 0 on right, doubling the number

Step 6: Right shift a by 2 (a >> 2)

a: 00001101
Right shift: 00000011 (3)

Why: Right shift moves bits right, dropping bits on right, dividing the number by 4

Result:

AND result: 8 (00001000)
OR result: 15 (00001111)
XOR result: 7 (00000111)
NOT a result: -14 (11110010)
Left shift a by 1: 26 (00011010)
Right shift a by 2: 3 (00000011)

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func main() {
	a := 13 // 00001101
	b := 10 // 00001010

	and := a & b // AND operation
	or := a | b  // OR operation
	xor := a ^ b // XOR operation
	not := ^a     // NOT operation
	leftShift := a << 1  // Left shift by 1
	rightShift := a >> 2 // Right shift by 2

	fmt.Printf("AND result: %d (%.8b)\n", and, and)
	fmt.Printf("OR result: %d (%.8b)\n", or, or)
	fmt.Printf("XOR result: %d (%.8b)\n", xor, xor)
	fmt.Printf("NOT a result: %d (%.8b)\n", not, uint8(not))
	fmt.Printf("Left shift a by 1: %d (%.8b)\n", leftShift, leftShift)
	fmt.Printf("Right shift a by 2: %d (%.8b)\n", rightShift, rightShift)
}

and := a & b // AND operation

combine bits keeping 1 only where both bits are 1

or := a | b // OR operation

combine bits keeping 1 where either bit is 1

xor := a ^ b // XOR operation

combine bits keeping 1 where bits differ

not := ^a // NOT operation

flip all bits of a

leftShift := a << 1 // Left shift by 1

move bits left by 1, add 0 on right

rightShift := a >> 2 // Right shift by 2

move bits right by 2, drop bits on right

Output

AND result: 8 (00001000)

OR result: 15 (00001111)

XOR result: 7 (00000111)

NOT a result: -14 (11110010)

Left shift a by 1: 26 (00011010)

Right shift a by 2: 3 (00000011)

Complexity Analysis

Time: O(1) because bit operations happen directly on fixed-size integers without loops

Space: O(1) because no extra memory is needed beyond variables

vs Alternative: Bit manipulation is much faster and uses less memory than arithmetic or string-based methods for similar tasks

Edge Cases

a or b is zero

AND results in 0, OR and XOR equal the non-zero number

DSA Go

and := a & b // AND operation

left shift causes bits to move out of range

bits shifted out are lost, result may wrap or become zero

DSA Go

leftShift := a << 1  // Left shift by 1

right shift on zero

result remains zero

DSA Go

rightShift := a >> 2 // Right shift by 2

When to Use This Pattern

When you need to quickly check, set, flip, or move bits inside numbers, use bit manipulation because it is fast and memory efficient.

Common Mistakes

Mistake: Confusing left shift with multiplication without considering overflow
Fix: Remember left shift doubles the number only if bits don't overflow the integer size

Mistake: Using NOT operator without understanding two's complement negative representation
Fix: Know that NOT flips bits and changes sign in two's complement, so result may be negative

Summary

Bit manipulation changes numbers by working directly on their bits using AND, OR, XOR, NOT, and shifts.

Use it when you want fast, low-level control over individual bits in numbers.

The key insight is that numbers are just bits, and simple rules on bits create powerful operations.

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