Bit Manipulation

Introduction to Bit Manipulation

Bit manipulation involves directly working with individual bits in binary representations of numbers. It’s essential for low-level programming, optimization, and working with hardware.

Bit manipulation is fundamental for:

Embedded systems and hardware control
Cryptography and hashing
Graphics and image processing
Network protocols
Performance optimization

Bitwise Operators

Basic Operators

Operator	Name	Description	Example
`&`	AND	Both bits must be 1	`5 & 3 = 1`
`\|`	OR	At least one bit must be 1	`5 \| 3 = 7`
`^`	XOR	Bits must be different	`5 ^ 3 = 6`
`~`	NOT	Inverts all bits	`~5 = -6`
`<<`	Left shift	Shift bits left	`5 << 1 = 10`
`>>`	Right shift	Shift bits right	`5 >> 1 = 2`

Visual Examples

  5 = 0101
  3 = 0011
  ---------
& = 0001 = 1  (AND)
| = 0111 = 7  (OR)
^ = 0110 = 6  (XOR)
~ = 1010 = -6 (NOT of 5, in two's complement)

Converting Binary to Unsigned Int

From 0-binary_to_uint.c:

#include "main.h"

/**
 * binary_to_uint - converts a binary number to an unsigned int
 * @b: pointer to a string of binary digits
 * Return: unsigned int
 */
unsigned int binary_to_uint(char *b)
{
    unsigned int n = 0;
    int i = 0;

    while (b[i] != '\0')
    {
        if (b[i] == '1')
            n = n * 2 + 1;
        else if (b[i] == '0')
            n = n * 2;
        else
            return (0);
        i++;
    }
    return (n);
}

How it works:

Input: "1011"

Step 1: n = 0, read '1' → n = 0 * 2 + 1 = 1
Step 2: n = 1, read '0' → n = 1 * 2 + 0 = 2
Step 3: n = 2, read '1' → n = 2 * 2 + 1 = 5
Step 4: n = 5, read '1' → n = 5 * 2 + 1 = 11

Result: 11 (decimal)

Usage:

unsigned int result;

result = binary_to_uint("1");        // 1
result = binary_to_uint("10");       // 2
result = binary_to_uint("1011");     // 11
result = binary_to_uint("10000000"); // 128
result = binary_to_uint("invalid");  // 0 (error)

Algorithm: This uses the property that reading binary left-to-right is like:

Multiply current result by 2 (shift left)
Add the current bit (0 or 1)

Example: 1011 = ((1×2 + 0)×2 + 1)×2 + 1 = 11

Printing Binary Representation

From 1-print_binary.c:

#include "main.h"

/**
 * print_binary - prints the binary representation of a number
 * @n: number to be converted
 * Return: void
 */
void print_binary(unsigned long int n)
{
    if (n >> 0)
    {
        if (n >> 1)
            print_binary(n >> 1);
        _putchar((n & 1) + '0');
    }
    else
    {
        _putchar('0');
    }
}

How it works:

Recursive approach: Process bits from left to right
Base case: n >> 1 is 0 (no more bits)
Extract bit: n & 1 gets the rightmost bit
Convert to char: + '0' converts 0/1 to ‘0’/‘1’

Example execution for print_binary(5):

5 = 0101

Call 1: n=5 (0101), n>>1=2 (not 0, recurse)
Call 2: n=2 (0010), n>>1=1 (not 0, recurse)
Call 3: n=1 (0001), n>>1=0 (base case)
  Print: 1 & 1 = 1 → '1'
Back to Call 2:
  Print: 2 & 1 = 0 → '0'
Back to Call 1:
  Print: 5 & 1 = 1 → '1'

Output: 101

Usage:

print_binary(0);   // Output: 0
print_binary(1);   // Output: 1
print_binary(5);   // Output: 101
print_binary(98);  // Output: 1100010
print_binary(255); // Output: 11111111

Getting a Specific Bit

From 2-get_bit.c:

#include "main.h"

/**
 * get_bit - returns the value of a bit at a given index
 * @n: number to be converted
 * @index: index of the bit to be returned
 * Return: 1 if the bit is 1, 0 if the bit is 0
 */
int get_bit(unsigned long int n, unsigned int index)
{
    unsigned long int mask;

    mask = 1 << index;
    return ((n & mask) >> index);
}

How it works:

Create mask: 1 << index puts 1 in the desired position
Apply mask: n & mask isolates that bit
Shift back: >> index moves bit to position 0

Example: Get bit 2 of 5 (binary 101)

n = 5 = 0101
index = 2

Step 1: mask = 1 << 2 = 0100
Step 2: n & mask = 0101 & 0100 = 0100
Step 3: 0100 >> 2 = 0001 = 1

Result: 1

Visual:

Number: 5 = 0 1 0 1
Index:      3 2 1 0

get_bit(5, 0) = 1
get_bit(5, 1) = 0
get_bit(5, 2) = 1
get_bit(5, 3) = 0

Setting a Bit to 1

From 3-set_bit.c:

#include "main.h"

/**
 * set_bit - sets the value of a bit to 1 at a given index
 * @n: number to be converted
 * @index: index of the bit to be set
 * Return: 1 if the bit was set, -1 if error occurred
 */
int set_bit(unsigned long int *n, unsigned int index)
{
    unsigned long int mask;

    if (index > 63)
        return (-1);

    mask = 1 << index;
    *n = *n | mask;
    return (1);
}

How it works:

Validate index: Check if index is within valid range (0-63 for 64-bit)
Create mask: 1 << index creates mask with 1 at position
OR operation: *n | mask sets the bit to 1

Example: Set bit 2 of 5

*n = 5 = 0101
index = 2

mask = 1 << 2 = 0100
*n | mask = 0101 | 0100 = 0101 = 5

Result: 5 (already set)

Example: Set bit 1 of 5

*n = 5 = 0101
index = 1

mask = 1 << 1 = 0010
*n | mask = 0101 | 0010 = 0111 = 7

Result: 7

OR operation for setting: OR with 1 always produces 1, regardless of the original bit value:

0 | 1 = 1 (bit was 0, now 1)
1 | 1 = 1 (bit was 1, stays 1)

Clearing a Bit (Set to 0)

From 4-clear_bit.c:

#include "main.h"

/**
 * clear_bit - clears the value of a bit at a given index
 * @n: number to be converted
 * @index: index of the bit to be cleared
 * Return: 1 if the bit was cleared, -1 if error occurred
 */
int clear_bit(unsigned long int *n, unsigned int index)
{
    unsigned long int mask;

    if (index > 63)
        return (-1);

    mask = ~(1 << index);
    *n = *n & mask;
    return (1);
}

How it works:

Create inverted mask: ~(1 << index) creates mask with 0 at position, 1s elsewhere
AND operation: *n & mask clears the bit

Example: Clear bit 2 of 7

*n = 7 = 0111
index = 2

Step 1: 1 << 2 = 0100
Step 2: ~(0100) = 1011
Step 3: 0111 & 1011 = 0011 = 3

Result: 3

AND operation for clearing: AND with 0 always produces 0:

0 & 0 = 0 (bit was 0, stays 0)
1 & 0 = 0 (bit was 1, now 0)

AND with 1 preserves the bit:

0 & 1 = 0
1 & 1 = 1

Counting Bits to Flip

From 5-flip_bits.c:

#include "main.h"

/**
 * flip_bits - returns the number of bits you would need to flip to get from
 * one number to another
 * @n: number to be converted
 * @m: number to be converted
 * Return: number of bits to flip
 */
unsigned int flip_bits(unsigned long int n, unsigned long int m)
{
    unsigned long int x = n ^ m;
    unsigned int count = 0;

    while (x)
    {
        count += x & 1;
        x >>= 1;
    }
    return (count);
}

How it works:

XOR operation: n ^ m produces 1 where bits differ
Count ones: Loop counts the 1 bits in the XOR result

Example: flip_bits(5, 3)

n = 5 = 0101
m = 3 = 0011
x = n ^ m = 0101 ^ 0011 = 0110

Count bits in 0110:
Iteration 1: x=0110, x&1=0, count=0, x>>=1 → x=0011
Iteration 2: x=0011, x&1=1, count=1, x>>=1 → x=0001
Iteration 3: x=0001, x&1=1, count=2, x>>=1 → x=0000

Result: 2 bits need to flip

Why XOR? XOR produces 1 when bits are different:

0 ^ 0 = 0 (same)
1 ^ 1 = 0 (same)
0 ^ 1 = 1 (different)
1 ^ 0 = 1 (different)

So n ^ m highlights exactly which bits need to change!

Common Bit Manipulation Patterns

Check if Bit is Set

if (n & (1 << k))
    printf("Bit %d is set\n", k);

Toggle a Bit

n ^= (1 << k);  // Flip bit k

Check if Number is Power of 2

if (n > 0 && (n & (n - 1)) == 0)
    printf("Power of 2\n");

Why it works:

= 1000
= 0111
& 7 = 0000 (power of 2)

= 0110
= 0101
& 5 = 0100 (not power of 2)

Count Set Bits (Population Count)

unsigned int count_bits(unsigned int n)
{
    unsigned int count = 0;
    while (n)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Swap Two Numbers Without Temp

a ^= b;
b ^= a;
a ^= b;
// a and b are swapped!

Why it works:

Initial: a=5, b=3
a ^= b  → a = 5^3 = 6, b = 3
b ^= a  → b = 3^6 = 5, a = 6
a ^= b  → a = 6^5 = 3, b = 5
Final: a=3, b=5 (swapped!)

Get Rightmost Set Bit

int rightmost = n & -n;

Example:

n = 12 = 1100
-n (two's complement) = 0100
n & -n = 1100 & 0100 = 0100 = 4

Clear Rightmost Set Bit

n &= (n - 1);

Example:

n = 12 = 1100
n - 1 = 11 = 1011
n & (n-1) = 1100 & 1011 = 1000 = 8

Bit Masks and Flags

Using Flags

#define READ    (1 << 0)  // 0001
#define WRITE   (1 << 1)  // 0010
#define EXECUTE (1 << 2)  // 0100
#define ADMIN   (1 << 3)  // 1000

unsigned int permissions = 0;

// Grant permissions
permissions |= READ;
permissions |= WRITE;
// permissions = 0011 (READ + WRITE)

// Check permission
if (permissions & WRITE)
    printf("Has write access\n");

// Revoke permission
permissions &= ~WRITE;
// permissions = 0001 (only READ)

// Toggle permission
permissions ^= EXECUTE;

Packing Multiple Values

// Pack RGB color (8 bits each) into 32-bit int
unsigned int rgb = (r << 16) | (g << 8) | b;

// Extract components
unsigned char red   = (rgb >> 16) & 0xFF;
unsigned char green = (rgb >> 8) & 0xFF;
unsigned char blue  = rgb & 0xFF;

Performance Considerations

Faster Operations

Multiply by 2: n << 1 faster than n * 2
Divide by 2: n >> 1 faster than n / 2
Check even/odd: n & 1 faster than n % 2
Clear low bits: n & ~mask efficient

Use Cases

Hardware register manipulation
Network protocol parsing
Compression algorithms
Cryptographic operations

Best Practices

Use meaningful constants

#define BIT_0 (1 << 0)
#define BIT_5 (1 << 5)

value |= BIT_5;  // Clear intent

Comment bit operations

// Set bit 3 to enable interrupt
reg |= (1 << 3);

Validate index ranges

if (index > 63)  // For 64-bit values
    return -1;

Use unsigned for bit operations

unsigned int flags;  // Good
int flags;           // Risky with shifts

Be careful with negative numbers

// Right shift of negative numbers is implementation-defined
int n = -5;
n >> 1;  // May not work as expected

Shift overflow: Shifting by >= the number of bits in the type is undefined behavior:

unsigned int n = 1;
n << 32;  // Undefined! (32-bit int has only 32 bits)

Common Mistakes

Forgetting Operator Precedence

// Wrong: & has lower precedence than ==
if (flags & FLAG == FLAG)  // Parsed as: flags & (FLAG == FLAG)

// Correct: use parentheses
if ((flags & FLAG) == FLAG)

Mixing Signed and Unsigned

int n = -1;           // 11111111 11111111 11111111 11111111
unsigned int u = n;   // Same bit pattern, but huge positive number!
printf("%u\n", u);   // 4294967295

Using >> for Division by 2 with Negatives

int n = -5;
int half = n >> 1;  // Implementation-defined, might not be -2

Key Takeaways

Bitwise operators work directly on binary representation
Use & for masking/testing, | for setting, ^ for toggling
Shifts are efficient multiply/divide by powers of 2
XOR useful for comparing, swapping, and encryption
Always validate index ranges when accessing specific bits
Use unsigned types for bit manipulation
Bit operations are essential for low-level programming

Preprocessor

Use macros for bit manipulation patterns

Structures & Typedef

Combine with bit fields in structures

Get Started

Fundamentals

Pointers & Memory

Advanced Concepts

Data Structures

System Programming

Introduction to Bit Manipulation

Bitwise Operators

Basic Operators

Visual Examples

Converting Binary to Unsigned Int

Printing Binary Representation

Getting a Specific Bit

Setting a Bit to 1

Clearing a Bit (Set to 0)

Counting Bits to Flip

Common Bit Manipulation Patterns

Check if Bit is Set

Toggle a Bit

Check if Number is Power of 2

Count Set Bits (Population Count)

Swap Two Numbers Without Temp

Get Rightmost Set Bit

Clear Rightmost Set Bit

Bit Masks and Flags

Using Flags

Packing Multiple Values

Performance Considerations

Faster Operations

Use Cases

Best Practices

Common Mistakes

Forgetting Operator Precedence

Mixing Signed and Unsigned

Using >> for Division by 2 with Negatives

Key Takeaways

Preprocessor

Structures & Typedef

Build docs developers (and LLMs) love

Get Started

Fundamentals

Pointers & Memory

Advanced Concepts

Data Structures

System Programming

​Introduction to Bit Manipulation

​Bitwise Operators

​Basic Operators

​Visual Examples

​Converting Binary to Unsigned Int

​Printing Binary Representation

​Getting a Specific Bit

​Setting a Bit to 1

​Clearing a Bit (Set to 0)

​Counting Bits to Flip

​Common Bit Manipulation Patterns

​Check if Bit is Set

​Toggle a Bit

​Check if Number is Power of 2

​Count Set Bits (Population Count)

​Swap Two Numbers Without Temp

​Get Rightmost Set Bit

​Clear Rightmost Set Bit

​Bit Masks and Flags

​Using Flags

​Packing Multiple Values

​Performance Considerations

Faster Operations

Use Cases

​Best Practices

​Common Mistakes

​Forgetting Operator Precedence

​Mixing Signed and Unsigned

​Using >> for Division by 2 with Negatives

​Key Takeaways

​Related Topics

Preprocessor

Structures & Typedef

Build docs developers (and LLMs) love

Introduction to Bit Manipulation

Bitwise Operators

Basic Operators

Visual Examples

Converting Binary to Unsigned Int

Printing Binary Representation

Getting a Specific Bit

Setting a Bit to 1

Clearing a Bit (Set to 0)

Counting Bits to Flip

Common Bit Manipulation Patterns

Check if Bit is Set

Toggle a Bit

Check if Number is Power of 2

Count Set Bits (Population Count)

Swap Two Numbers Without Temp

Get Rightmost Set Bit

Clear Rightmost Set Bit

Bit Masks and Flags

Using Flags

Packing Multiple Values

Performance Considerations

Best Practices

Common Mistakes

Forgetting Operator Precedence

Mixing Signed and Unsigned

Using >> for Division by 2 with Negatives

Key Takeaways

Related Topics