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

Overview - Bit Manipulation Basics AND OR XOR NOT Left Right Shift

What is it?

Bit manipulation is working directly with the tiny pieces inside numbers called bits, which are 0s and 1s. It uses simple operations like AND, OR, XOR, NOT, and shifting bits left or right to change or check these bits. These operations help computers do tasks faster and use less memory. Bit manipulation is like controlling the smallest switches inside a number to get the exact result you want.

Why it matters

Without bit manipulation, computers would have to use slower, bigger steps to do simple tasks like checking if a number is even or odd, or turning features on and off in a program. Bit manipulation makes programs faster and smaller, which is very important in games, phones, and devices with limited power. It helps programmers solve problems that need quick decisions or compact data storage.

Where it fits

Before learning bit manipulation, you should understand basic number systems like decimal and binary. After this, you can learn about more complex data structures like sets and flags, or algorithms that use bits to solve problems efficiently.

Mental Model

Core Idea

Bit manipulation is like flipping tiny switches inside a number to quickly change or check its parts using simple rules.

Think of it like...

Imagine a row of light switches in your house. Each switch can be ON (1) or OFF (0). Bit manipulation is like turning these switches on or off, or checking which ones are on, to control the lights exactly how you want.

Number bits:  1 0 1 1 0 0 1 0
Positions:    7 6 5 4 3 2 1 0
Operations:
AND (&): keeps switches ON only if both are ON
OR  (|): turns switches ON if either is ON
XOR (^): flips switches ON if only one is ON
NOT (~): flips all switches
Shift <<: moves switches left, adding OFF on right
Shift >>: moves switches right, adding OFF or sign bit on left

Build-Up - 7 Steps

1

Foundation

Understanding Binary Numbers

Concept: Introduce how numbers are stored as bits (0s and 1s) in computers.

Every number in a computer is stored as a series of bits. For example, the number 6 in binary is 00000110, where each bit represents a power of two. The rightmost bit is the smallest (2^0), and the leftmost is the largest (2^7 for an 8-bit number).

Result

You can see that 6 is 00000110 in bits.

Understanding binary is essential because bit manipulation works directly on these bits, not on the decimal numbers we usually see.

2

Foundation

Basic Bitwise Operators Explained

Concept: Learn the four main bitwise operators: AND, OR, XOR, and NOT.

AND (&) compares two bits and returns 1 only if both bits are 1. OR (|) returns 1 if at least one bit is 1. XOR (^) returns 1 if exactly one bit is 1. NOT (~) flips every bit from 0 to 1 or 1 to 0. Example: 5 (0101) & 3 (0011) = 1 (0001).

Result

Applying 5 & 3 gives 1 in bits: 0001.

Knowing these operators lets you combine or change bits in precise ways, which is the foundation of bit manipulation.

3

Intermediate

Using Bit Shifts to Multiply and Divide

🤔Before reading on: do you think shifting bits left by 1 doubles a number or halves it? Commit to your answer.

Concept: Bit shifts move bits left or right, which can multiply or divide numbers by powers of two.

Left shift (<<) moves bits to the left, adding zeros on the right. This multiplies the number by 2 for each shift. Right shift (>>) moves bits to the right, removing bits on the right. This divides the number by 2 for each shift, ignoring remainders. Example: 4 (0100) << 1 = 8 (1000), 8 >> 2 = 2 (0010).

Result

4 << 1 = 8, 8 >> 2 = 2

Understanding shifts as fast multiply/divide helps optimize code and understand low-level data operations.

4

Intermediate

Combining Operators for Bit Flags

🤔Before reading on: do you think OR or AND is better to turn on a specific bit without changing others? Commit to your answer.

Concept: Use bitwise operators to set, clear, or toggle specific bits in a number acting as flags.

To turn on a bit, use OR with a mask that has 1 at the bit position. To turn off a bit, use AND with the mask's NOT. To toggle a bit, use XOR with the mask. Example: number=8 (1000), turn on bit 1 (mask=0010): 8 | 2 = 10 (1010).

Result

Turning on bit 1 in 8 results in 10 (1010).

This shows how bits can represent multiple on/off options compactly and be changed individually.

5

Intermediate

Checking Bits with AND Operator

🤔Before reading on: do you think AND with a mask returns the bit value or a boolean true/false? Commit to your answer.

Concept: Use AND to check if a specific bit is on by masking all other bits.

To check if bit n is on, AND the number with (1 << n). If the result is not zero, the bit is on. Example: number=10 (1010), check bit 1: 10 & 2 = 2 (not zero), so bit 1 is on.

Result

Bit 1 in 10 is ON because 10 & 2 = 2.

This technique is essential for reading specific bits without changing the number.

6

Advanced

Using NOT and Two's Complement

🤔Before reading on: do you think NOT flips bits and changes the number's sign or just flips bits without sign change? Commit to your answer.

Concept: NOT flips all bits, but in signed numbers, this relates to two's complement representation and affects the sign.

In two's complement, negative numbers are stored by flipping bits and adding one. Applying NOT (~) flips bits, which changes positive numbers to negative ones minus one. Example: 5 (00000101) NOT is -6 (11111010 in 8-bit two's complement).

Result

~5 = -6 in two's complement

Understanding two's complement is key to correctly using NOT and interpreting negative numbers in bit manipulation.

7

Expert

Bit Manipulation Tricks for Performance

🤔Before reading on: do you think XOR can be used to swap two numbers without a temporary variable? Commit to your answer.

Concept: Advanced tricks use bitwise operations to optimize code, like swapping variables without extra space or checking parity quickly.

Swapping two numbers a and b: a = a ^ b b = a ^ b a = a ^ b This swaps values without a temporary variable. Other tricks include checking if a number is a power of two using (n & (n-1)) == 0.

Result

Swapping 5 and 3 using XOR results in a=3, b=5 without extra memory.

These tricks show how bit manipulation can reduce memory use and speed up critical code sections.

Under the Hood

Bitwise operations work directly on the binary representation of numbers stored in the computer's memory. Each bit corresponds to a physical switch in the processor's circuits. When an operation like AND or OR is performed, the processor applies simple logic gates to each pair of bits simultaneously. Shifts move bits left or right by rewiring which bit position maps to which output, often implemented by fast hardware shifters. Two's complement encoding allows signed numbers to be represented so that arithmetic and bitwise operations work uniformly.

Why designed this way?

Bit manipulation was designed to allow very fast, low-level control of data using minimal hardware resources. Early computers had limited memory and processing power, so using bits directly saved space and time. Two's complement was chosen because it simplifies arithmetic operations and hardware design, avoiding separate circuits for subtraction and negative numbers. Bitwise operators provide a universal, simple set of tools to manipulate data efficiently.

┌───────────────┐
│   Number bits │
│  0 1 0 1 1 0 0 1  │
└─────┬─────────┘
      │
      ▼
┌───────────────┐
│ Bitwise Logic │
│ AND, OR, XOR, │
│ NOT, SHIFT    │
└─────┬─────────┘
      │
      ▼
┌───────────────┐
│  Result bits  │
│  1 0 1 0 0 1 1 0  │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does shifting bits right always divide a number by two exactly? Commit to yes or no.

Common Belief: Right shifting a number always divides it by two exactly.

Reality: Right shifting divides by two but discards any remainder, effectively performing floor division for positive numbers. For negative numbers, behavior depends on the language and sign extension.

Why it matters: Assuming exact division can cause bugs in calculations, especially with negative numbers or when precision matters.

Quick: Does XORing a number with itself always give zero? Commit to yes or no.

Common Belief: XORing a number with itself sometimes gives the same number back.

Reality: XORing any number with itself always results in zero because bits cancel out.

Why it matters: Misunderstanding this can lead to incorrect logic in algorithms that rely on XOR properties.

Quick: Does NOT operator just flip bits without affecting the number's sign? Commit to yes or no.

Common Belief: NOT operator flips bits but does not change whether the number is positive or negative.

Reality: NOT flips bits and in two's complement changes the sign and value, often resulting in negative numbers.

Why it matters: Ignoring sign changes can cause unexpected negative values and bugs in arithmetic.

Quick: Can you use OR to turn off a bit in a number? Commit to yes or no.

Common Belief: Using OR can turn off bits by setting them to zero.

Reality: OR can only turn bits on (set to 1), never off. To turn off bits, you must use AND with a mask.

Why it matters: Using OR incorrectly to clear bits will fail silently, causing wrong data states.

Expert Zone

1

Bit shifts on signed integers can behave differently across languages due to sign extension, which can cause subtle bugs if not handled carefully.

2

Using XOR to swap variables is clever but often less readable and sometimes slower on modern CPUs with optimized instructions.

3

Two's complement representation means that NOT and negation are related but not the same; understanding this helps avoid off-by-one errors.

When NOT to use

Bit manipulation is not suitable when code readability and maintainability are more important than performance, or when working with complex data types like floating-point numbers. In such cases, use higher-level abstractions or libraries. Also, avoid bit tricks in security-sensitive code without thorough review, as they can introduce subtle bugs.

Production Patterns

Bit manipulation is widely used in embedded systems for hardware control, in graphics programming for color and pixel operations, in compression algorithms to pack data tightly, and in cryptography for fast transformations. Professionals also use bit flags to represent multiple boolean options compactly in configuration settings.

Connections

Boolean Algebra

Bitwise operators are the digital form of Boolean logic operations.

Understanding Boolean algebra helps grasp how AND, OR, and XOR work at the bit level, bridging math and computer science.

Digital Electronics

Bit manipulation corresponds directly to logic gates and circuits in hardware.

Knowing how bits map to physical switches and gates deepens understanding of how software controls hardware.

Set Theory

Bit flags represent sets where each bit indicates presence or absence of an element.

This connection helps in designing efficient algorithms for set operations using bitwise logic.

Common Pitfalls

#1 Trying to clear a bit using OR instead of AND.

Wrong approach:

number = number | (1 << bitPosition) // This turns bit on, not off

Correct approach:

number = number & ^(1 << bitPosition) // This clears the bit

Root cause:

Confusing OR's ability to set bits with clearing bits, misunderstanding how masks work.

#2 Assuming right shift always divides by two correctly for negative numbers.

Wrong approach:

result = negativeNumber >> 1 // May not behave as expected due to sign extension

Correct approach:

Use arithmetic right shift or explicit division for signed numbers to avoid errors

Root cause:

Not knowing that right shift behavior depends on sign and language implementation.

#3 Using NOT operator and expecting positive results.

Wrong approach:

result = ^number // expecting positive flipped bits

Correct approach:

result = ^number // but remember this changes sign in two's complement

Root cause:

Ignoring two's complement representation and sign changes when flipping bits.

Key Takeaways

Bit manipulation works directly on the smallest units of data, bits, allowing fast and memory-efficient operations.

AND, OR, XOR, and NOT are the basic tools to combine and change bits in predictable ways.

Shifting bits left or right multiplies or divides numbers by powers of two, but watch out for sign and overflow issues.

Bit flags let you store many true/false options compactly and change them individually using bitwise operators.

Understanding two's complement is crucial to correctly interpret results of NOT and shifts on signed numbers.

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