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

Mental Model

Bit manipulation changes numbers by flipping or moving their tiny on/off switches called bits.

Analogy: Imagine a row of light switches where each switch can be on or off. Bit operations flip, combine, or shift these switches to get new patterns.

Number 13 in bits (8 bits):
0 0 0 0 1 1 0 1
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
7 6 5 4 3 2 1 0 (bit positions)

Dry Run Walkthrough

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

Goal: Show results of AND, OR, XOR, NOT, left shift, and right shift on a and b

Step 1: Calculate a AND b

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

Why: AND keeps bits on only if both a and b have them on

Step 2: Calculate a OR b

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

Why: OR turns bits on if either a or b has them on

Step 3: Calculate a XOR b

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

Why: XOR turns bits on only if a and b differ at that bit

Step 4: Calculate NOT a (invert bits)

a = 00001101
NOT a = 11110010 (242)

Why: NOT flips every bit from on to off or off to on

Step 5: Left shift a by 1 (multiply by 2)

a = 00001101
Left shift by 1 = 00011010 (26)

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

Step 6: Right shift a by 2 (divide by 4)

a = 00001101
Right shift by 2 = 00000011 (3)

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

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdint.h>

void print_bits(uint8_t n) {
    for (int i = 7; i >= 0; i--) {
        printf("%d", (n >> i) & 1);
    }
}

int main() {
    uint8_t a = 13; // 00001101
    uint8_t b = 10; // 00001010

    uint8_t and_result = a & b; // bitwise AND
    uint8_t or_result = a | b;  // bitwise OR
    uint8_t xor_result = a ^ b; // bitwise XOR
    uint8_t not_result = ~a;    // bitwise NOT
    uint8_t left_shift = a << 1; // left shift by 1
    uint8_t right_shift = a >> 2; // right shift by 2

    printf("a = "); print_bits(a); printf(" (%d)\n", a);
    printf("b = "); print_bits(b); printf(" (%d)\n", b);

    printf("a AND b = "); print_bits(and_result); printf(" (%d)\n", and_result);
    printf("a OR b = "); print_bits(or_result); printf(" (%d)\n", or_result);
    printf("a XOR b = "); print_bits(xor_result); printf(" (%d)\n", xor_result);
    printf("NOT a = "); print_bits(not_result); printf(" (%d)\n", not_result);
    printf("a << 1 = "); print_bits(left_shift); printf(" (%d)\n", left_shift);
    printf("a >> 2 = "); print_bits(right_shift); printf(" (%d)\n", right_shift);

    return 0;
}

uint8_t and_result = a & b;

compute bitwise AND to keep bits on only if both a and b have them on

uint8_t or_result = a | b;

compute bitwise OR to turn bits on if either a or b has them on

uint8_t xor_result = a ^ b;

compute bitwise XOR to turn bits on only if bits differ

uint8_t not_result = ~a;

compute bitwise NOT to flip every bit

uint8_t left_shift = a << 1;

left shift bits by 1 to multiply by 2

uint8_t right_shift = a >> 2;

right shift bits by 2 to divide by 4

Output

a = 00001101 (13)

b = 00001010 (10)

a AND b = 00001000 (8)

a OR b = 00001111 (15)

a XOR b = 00000111 (7)

NOT a = 11110010 (242)

a << 1 = 00011010 (26)

a >> 2 = 00000011 (3)

Complexity Analysis

Time: O(1) because bitwise operations work on fixed-size bits directly

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Bit manipulation is much faster and uses less memory than arithmetic operations for these tasks

Edge Cases

a = 0 (all bits off)

AND, OR, XOR with any number behave as expected; NOT flips all bits to 1

DSA C

uint8_t not_result = ~a;

left shift causes bits to overflow beyond 8 bits

bits shifted out are lost, result wraps around in 8 bits

DSA C

uint8_t left_shift = a << 1;

right shift on zero

result remains zero as bits shifted in are zeros

DSA C

uint8_t right_shift = a >> 2;

When to Use This Pattern

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

Common Mistakes

Mistake: Using signed integers for bit shifts causing unexpected sign extension
Fix: Use unsigned integers like uint8_t to avoid sign issues

Mistake: Confusing left shift with multiplication without considering overflow
Fix: Remember left shift can lose bits if they move beyond the fixed size

Summary

Bit manipulation changes numbers by flipping or moving their bits using AND, OR, XOR, NOT, and shifts.

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

Think of bits as tiny switches you can combine or move to get new numbers quickly.

Practice

1. What is the result of the bitwise AND operation between 5 and 3? (5 = 0101, 3 = 0011 in binary)

easy

A. 0

B. 1

C. 6

D. 7

Solution

1. Step 1: Convert numbers to binary

   5 in binary is 0101, and 3 in binary is 0011.

2. Step 2: Perform bitwise AND operation

   0101 AND 0011 = 0001 (only bits set in both numbers remain set).

3. Final Answer:

   1 -> Option B

4. Quick Check:

   5 & 3 = 1 [OK]

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

Common Mistakes:

• Confusing AND with OR operation
• Not converting decimal to binary correctly
• Mixing bit positions during calculation

2. Which of the following is the correct syntax for left shifting the integer x by 2 bits in C?

easy

A. x >> 2;

B. x <<< 2;

C. x << 2;

D. x >> 2 <<;

Solution

1. Step 1: Understand left shift operator in C

   The left shift operator is written as << and shifts bits to the left.

2. Step 2: Check syntax correctness

   x << 2; uses x << 2; which correctly shifts bits of x left by 2 positions.

3. Final Answer:

   x << 2; -> Option C

4. Quick Check:

   Left shift syntax = x << 2; [OK]

Hint: Use << for left shift, >> for right shift [OK]

Common Mistakes:

• Using >>> which is invalid in C
• Confusing left shift with right shift
• Incorrect operator placement or syntax

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

int x = 6; // binary 0110
int y = x ^ 3; // 3 = 0011
printf("%d", y);

medium

A. 9

B. 7

C. 1

D. 5

Solution

1. Step 1: Convert numbers to binary and apply XOR

   6 in binary is 0110, 3 is 0011. XOR operation: 0110 ^ 0011 = 0101.

2. Step 2: Calculate decimal value of XOR result

   0101 in binary equals 5 decimal.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   6 ^ 3 = 5 [OK]

Hint: XOR flips bits where bits differ [OK]

Common Mistakes:

• Mixing XOR with OR or AND
• Incorrect binary conversion
• Misreading bit positions

4. Identify the error in the following C code snippet:

int x = 8;
int y = ~x << 1;
printf("%d", y);

medium

A. Using ~ operator without parentheses causes wrong shift

B. Missing semicolon after declaration

C. Shift operator << cannot be used with ~ operator

D. No error, code runs correctly

Solution

1. Step 1: Understand operator precedence

   The bitwise NOT (~) has higher precedence than shift (<<), so ~x is evaluated first.

2. Step 2: Check if parentheses needed

   Without parentheses, ~x is computed, then shifted left. This is correct but may cause confusion if intended differently.

3. Step 3: Identify common mistake

   If intention was to shift x first then NOT, parentheses are needed. Otherwise, no syntax error but logic may be wrong.

4. Final Answer:

   Using ~ operator without parentheses causes wrong shift -> Option A

5. Quick Check:

   Operator precedence matters; use parentheses [OK]

Hint: Use parentheses to control bitwise operation order [OK]

Common Mistakes:

• Ignoring operator precedence
• Assuming shift applies before NOT
• Thinking code has syntax error when it doesn't

5. Given an integer n, which expression correctly checks if the 3rd bit (from right, zero-based) is set (1)?

hard

A. (n & (1 << 3)) != 0

B. (n | (1 << 3)) == 0

C. (n ^ (1 << 3)) == 0

D. (n >> 3) & 1 == 0

Solution

1. Step 1: Understand bit position and mask

   The 3rd bit (zero-based) means bit at position 3. Mask is 1 shifted left by 3: (1 << 3) = 8.

2. Step 2: Check if bit is set using AND

   Using (n & (1 << 3)) checks if that bit is 1. If result is not zero, bit is set.

3. Final Answer:

   (n & (1 << 3)) != 0 -> Option A

4. Quick Check:

   Bit check uses AND with mask [OK]

Hint: Use AND with (1 << bit_position) to check bit [OK]

Common Mistakes:

• Using OR or XOR instead of AND for checking
• Wrong bit position shift
• Comparing shifted bit to zero incorrectly