Bit Manipulation in C

Bit Manipulation is one of the most important topics for coding interviews, competitive programming, embedded systems, operating systems, networking, game engines, device drivers, and low-level software development.

Many programmers know the formulas but do not understand why they work. In interviews, understanding the underlying logic is much more important than simply memorizing formulas.

What is a Bit?

A bit is the smallest unit of data in a computer. It can only hold one of two possible values:

• 0
• 1

Memory Representation

Suppose we declare an integer in C:

int num = 10;

The standard decimal number 10 is represented in binary format as 1010. In its explicit 8-bit representation, it looks like this:

00001010

When working with positions, we number them from right to left starting at 0:

Position: 7  6  5  4  3  2  1  0
Binary:   0  0  0  0  1  0  1  0

Looking at the breakdown above:

• Bit 3 = 1
• Bit 2 = 0
• Bit 1 = 1
• Bit 0 = 0

Why Bit Manipulation?

Normally, when you want to increment a value, you might write:

a = a + 1;

While this is highly readable, the CPU fundamentally performs all operations using bits underneath. Performing raw bit operations directly yields several core benefits:

• Faster: They execute directly on the hardware in fewer CPU cycles.
• Memory Efficient: Allows packing multiple flags or fields tightly into a single primitive variable.
• Hardware Native: Mimics logic gates directly.
• Extensively used in embedded systems, operating systems, networking protocols, and real-time graphics engines.

Bitwise Operators

C provides a rich set of built-in operators specifically for mutating bits directly:

Operator	Name
&	AND
|	OR
^	XOR
~	NOT
<<	Left Shift
>>	Right Shift

Understanding AND (&)

The bitwise AND operator compares corresponding bits and yields 1 if and only if both bits are 1.

Truth Table:

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

Example: 10 & 7

   10 = 1010
    7 = 0111
  --------------
  Result = 0010  (Decimal 2)

Understanding OR (|)

The bitwise OR operator returns 1 if at least one of the compared bits is 1.

Truth Table:

A	B	A | B
0	0	0
0	1	1
1	0	1
1	1	1

Example: 10 | 7

   10 = 1010
    7 = 0111
  --------------
  Result = 1111  (Decimal 15)

Understanding XOR (^)

The bitwise Exclusive OR (XOR) evaluates to 1 if the input bits are different, and 0 if they are the same.

Truth Table:

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

Crucial Rule to Remember: Same bits yield 0; different bits yield 1.

Example: 10 ^ 7

   10 = 1010
    7 = 0111
  --------------
  Result = 1101  (Decimal 13)

Understanding Left Shift (<<)

Shifts the bit pattern to the left by the specified number of positions, appending 0s to the right side.

Example: 5 << 1

Binary:     00000101  (Decimal 5)
Shift Left: 00001010  (Decimal 10)

Mathematical Rule:

• n << 1 evaluates to $n \times 2$
• n << 2 evaluates to $n \times 4$
• n << 3 evaluates to $n \times 8$

Understanding Right Shift (>>)

Shifts the bit pattern to the right, discarding bits that drop off the right boundary.

Example: 8 >> 1

Binary:      00001000  (Decimal 8)
Shift Right: 00000100  (Decimal 4)

Mathematical Rule:

• n >> 1 evaluates to $\lfloor n / 2 \rfloor$
• n >> 2 evaluates to $\lfloor n / 4 \rfloor$

---

1. Set Bit

To "Set" a bit means forcing its state to become 1, regardless of whether it was already 1 or 0.

Formula:

num | (1 << position)

Why It Works

Suppose num = 10 (Binary 1010). We want to set the bit at position 2.

1. Create a mask by shifting 1 left by 2 positions: 1 << 2 yields 0100.
2. Apply the bitwise OR operator between our number and the mask:

   1010  (num)
   0100  (mask)
  ------
   1110  (Decimal 14)

Code Implementation:

#include <stdio.h>

int main() 
{
    int num = 10;
    int pos = 2;

    num = num | (1 << pos);
    printf("%d", num); // Output: 14

    return 0;
}

2. Clear Bit

To "Clear" a bit means modifying it to become 0.

Formula:

num & ~(1 << position)

Why It Works

Suppose num = 14 (Binary 1110). We want to clear the bit at position 2.

1. Generate the bit mask: 1 << 2 yields 0100.
2. Apply bitwise NOT (~) to invert the mask: ~0100 becomes 1011.
3. Apply a bitwise AND operator:

   1110  (num)
   1011  (inverted mask)
  ------
   1010  (Decimal 10)

Code Implementation:

#include <stdio.h>

int main() 
{
    int num = 14;
    int pos = 2;

    num = num & ~(1 << pos);
    printf("%d", num); // Output: 10

    return 0;
}

3. Toggle Bit

To "Toggle" a bit means inverting its state: changing 0 to 1, and 1 to 0.

Formula:

num ^ (1 << position)

Why XOR?

Recall the rules of XOR: 0 ^ 1 = 1 and 1 ^ 1 = 0. This is exactly what we need to safely swap states without knowing the current state.

   1010  (num: 10)
   0100  (mask: 1 << 2)
  ------
   1110  (Decimal 14)

Code Implementation:

#include <stdio.h>

int main() 
{
    int num = 10;
    int pos = 2;

    num = num ^ (1 << pos);
    printf("%d", num); // Output: 14

    return 0;
}

Check Whether Bit is Set

This is a foundational interview favorite. We check the status of a precise bit by isolating it.

Formula:

num & (1 << position)

If the evaluated outcome is 0, the targeted bit is OFF (0). Otherwise, it is ON (1).

Code Implementation:

#include <stdio.h>

int main() 
{
    int num = 10;
    int pos = 3;

    if(num & (1 << pos))
        printf("Set");
    else
        printf("Not Set"); // Output: Set

    return 0;
}

---

Problem 1: Power of Two

Question: Check whether a given integer is a power of 2 (e.g., 1, 2, 4, 8, 16, 32, 64...).

Observation

Any positive number that represents an exact power of two contains exactly one set bit in its binary format.

1  = 0001
2  = 0010
4  = 0100
8  = 1000

Amazing Trick

Evaluate using the expression: n & (n-1). For any power of two, the output will always result in exactly 0.

Example with 8:

8 = 1000
7 = 0111
----------
8 & 7 = 0000  (Matches: is a power of 2)

Example with 12:

12 = 1100
11 = 1011
----------
12 & 11 = 1000  (Not zero: not a power of 2)

Code Implementation

#include <stdio.h>

int main() 
{
    int n = 16;

    if(n > 0 && (n & (n-1)) == 0)
        printf("Power of Two");
    else
        printf("Not Power of Two");

    return 0;
}

Time Complexity: $O(1)$ — executed in constant time without any looping structures.

Problem 2: Count Set Bits

Question: Count the total number of 1s present in the binary expansion of an integer.

Example: 13 in binary is 1101, which has 3 set bits.

Method 1: Simple Iterative Approach

Check every single bit by continuously checking the rightmost bit and shifting rightward.

#include <stdio.h>

int main() 
{
    int n = 13;
    int count = 0;

    while(n) {
        count += n & 1;
        n = n >> 1;
    }
    printf("%d", count); // Output: 3
    return 0;
}

Time Complexity: $O(\text{number of bits})$ (e.g., $O(32)$ for a standard 32-bit integer).

Method 2: Brian Kernighan's Algorithm

This is a highly popular interview technique that speeds up processing considerably.

Logic

The statement n = n & (n-1) actively clears the rightmost set bit of n. By looping until n reaches zero, the number of cycles equals the exact number of set bits.

Tracing 13 (1101)

• Step 1: 1101 & 1100 $\rightarrow$ 1100 (Count = 1)
• Step 2: 1100 & 1011 $\rightarrow$ 1000 (Count = 2)
• Step 3: 1000 & 0111 $\rightarrow$ 0000 (Count = 3. Loop finishes).

Code Implementation

#include <stdio.h>

int main() 
{
    int n = 13;
    int count = 0;

    while(n) {
        n = n & (n-1);
        count++;
    }
    printf("%d", count); // Output: 3
    return 0;
}

Time Complexity: $O(\text{Number of Set Bits})$ — much faster when numbers have sparse bits.

Problem 3: Find the Unique Number

Question: In a given array, every element appears exactly twice except for one single element. Locate that unique number.

Example Array: 1, 2, 3, 2, 1 → Answer: 3

XOR Properties

• Property 1: $A \oplus A = 0$ (Any number XORed with itself cancels out).
• Property 2: $A \oplus 0 = A$ (Any number XORed with 0 stays unchanged).
• Property 3: Commutative property ($A \oplus B = B \oplus A$).

Example Tracing

Calculation: 1 ^ 2 ^ 3 ^ 2 ^ 1
Rearranged:  (1 ^ 1) ^ (2 ^ 2) ^ 3
Evaluates:   0 ^ 0 ^ 3 = 3

Code Implementation

#include <stdio.h>

int main() 
{
    int arr[] = {1, 2, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = 0;

    for(int i = 0; i < n; i++) {
        result ^= arr[i];
    }
    printf("%d", result); // Output: 3
    return 0;
}

Time Complexity: $O(N)$ runtime with $O(1)$ auxiliary memory usage, vastly superior to $O(N^2)$ nested-loop lookups.

---

Interview-Level Bit Tricks

Check Odd or Even

if (n & 1) { /* Number is Odd */ }

Reason: The least significant bit (index 0) of every odd number is 1, while for even numbers it is always 0.

Multiply by 2

n << 1;

Divide by 2

n >> 1;

In-Place Variable Swapping

a = a ^ b;
b = a ^ b;
a = a ^ b;

Interview Tip: While this trick is great for interviews, normal code typically leverages an explicit temporary storage variable for better readability and compiler safety.

Summary Formula Reference Cheat-Sheet

Operation	Formula
Set Bit	n | (1 << pos)
Clear Bit	n & ~(1 << pos)
Toggle Bit	n ^ (1 << pos)
Check Bit	n & (1 << pos)
Power of Two Check	(n & (n-1)) == 0
Clear Lowest Set Bit	n = n & (n-1)
Odd / Even Check	n & 1
Fast Multiply by 2	n << 1
Fast Divide by 2	n >> 1

Core Interview Insight

Almost every complex bitwise problem asked in high-stakes interviews relies fundamentally on combining just three primary building blocks:

1. Mask Construction: Safely isolating target positions via (1 << position).
2. Basic Bit Logic: Leveraging foundational truths across &, |, ^, and ~.
3. Unique Algebra Rules: Exploiting key relationships like n & (n-1) and self-canceling terms ($A \oplus A = 0$).

Mastering these simple axioms provides the tools needed to approach advanced technical problems such as Missing Number, Single Number II, Two Unique Numbers, Subset Generation using Bitmasks, and optimized Bitmask DP with absolute confidence.

Frequently Asked Questions (FAQs)

1. Why are bitwise operations preferred over arithmetic operations in low-level code?

Bitwise operations match how logic gates inside the CPU operate natively. They don't require complex arithmetic pipelines, making them incredibly fast and useful for execution-critical software like embedded drivers or game rendering engines.

2. What happens if you try to left-shift a number beyond its datatype size boundary?

In C, shifting by a count that is greater than or equal to the total bit-width of the variable results in undefined behavior. It's vital to ensure shift boundaries stay within standard structural sizes (e.g., up to 31 shifts for standard 32-bit signed integers).

3. How does Brian Kernighan's algorithm optimize set bit counting?

Instead of iterating over every single bit position regardless of value, Brian Kernighan's method jumps directly from one set bit to the next by systematically clearing the lowest active bit via n & (n-1). This reduces total loop counts drastically for sparse bit configurations.

4. What is the difference between Logical Right Shift and Arithmetic Right Shift?

Logical Right Shift moves all bits to the right and pads 0 into the newly vacant spaces on the left (used for unsigned types). Arithmetic Right Shift preserves the sign bit by padding the left spaces with copies of the original sign bit (used for signed integers to maintain negative parity).