PROBLEM SOLVING - BIT MANIPULATION IN C

Bit Manipulation Basics in C

Bitwise Operators

C provides six bitwise operators for manipulating data at the bit level:

AND (&) - Sets bit to 1 if both bits are 1
OR (|) - Sets bit to 1 if either bit is 1
XOR (^) - Sets bit to 1 if bits are different
NOT (~) - Inverts all bits
Left Shift (<<) - Shifts bits left, fills with 0
Right Shift (>>) - Shifts bits right

// Examples:
unsigned char a = 5;    // 00000101
unsigned char b = 3;    // 00000011
unsigned char c = a & b; // 00000001 (1)
unsigned char d = a | b; // 00000111 (7)

Applications

Bit manipulation is crucial in many areas:

Low-level device control
Data compression
Cryptography
Graphics programming
Network protocols
Memory optimization
Performance-critical code

Common Techniques

Essential bit manipulation techniques:

// Set nth bit: num |= (1 << n)
// Clear nth bit: num &= ~(1 << n)
// Toggle nth bit: num ^= (1 << n)
// Check nth bit: (num >> n) & 1
// Multiply by 2^n: num << n
// Divide by 2^n: num >> n
// Swap without temp: a ^= b; b ^= a; a ^= b;

Bit Masking

Bit masks are used to extract or modify specific bits:

Extracting bits - Use AND with mask
Setting bits - Use OR with mask
Clearing bits - Use AND with inverted mask
Toggling bits - Use XOR with mask

// Extract lower 4 bits
unsigned char lower_nibble = byte & 0x0F;

// Set high nibble
byte |= 0xF0;

// Clear bits 3-5
byte &= ~(0x07 << 3);

PROBLEM SOLVING - BIT MANIPULATION TRICKS

#	Technique	Use Case	Approach	Complexity	Examples
1	Power of 2 Check	Determine if number is power of two	n & (n-1) == 0 and n != 0	O(1)	Optimization Memory alignment
2	Count Set Bits	Count number of 1 bits in number	Brian Kernighan's algorithm: n &= (n-1)	O(k)	Hamming weight Error detection
3	Swap Numbers	Swap two numbers without temp variable	XOR swap algorithm	O(1)	Low-memory environments Embedded systems
4	Find Single Number	Find non-duplicate in array of duplicates	XOR all elements in array	O(n)	Error detection Cryptography
5	Bit Masking	Extract or modify specific bits	Use AND, OR, XOR with bit masks	O(1)	Hardware registers Flags storage
6	Bit Fields	Efficient storage of multiple values	struct with bit field specification	O(1)	Memory optimization Network protocols
7	Endianness	Convert between big/little endian	Byte swapping with shifts	O(1)	Network programming Cross-platform code
8	Bit Rotation	Circular shift of bits	Combine left/right shifts with OR	O(1)	Cryptography Hash functions

Common Bit Operations

Set Bit

// Set nth bit
num |= (1 << n);

Time Complexity: O(1)

Clear Bit

// Clear nth bit
num &= ~(1 << n);

Time Complexity: O(1)

Toggle Bit

// Toggle nth bit
num ^= (1 << n);

Time Complexity: O(1)

Check Bit

// Check if nth bit is set
if (num & (1 << n)) {
    // Bit is set
}

Time Complexity: O(1)

Count Set Bits

int count = 0;
while (num) {
    num &= (num - 1);
    count++;
}
printf("Set bits: %d", count);

Time Complexity: O(k)

Power of 2 Check

if (num && !(num & (num - 1))) {
    printf("Power of 2");
} else {
    printf("Not power of 2");
}

Time Complexity: O(1)

Advanced Bit Techniques

#	Technique	Description	Use Case
1	Bitboard	Represent game states as bits for efficient processing	Game programming, chess engines
2	Hamming Distance	Count positions where bits differ between two numbers	Error detection, cryptography
3	Gray Code	Binary numeral system where successive values differ by one bit	Digital communications, encoders
4	Bitwise Sieve	Memory-efficient prime number sieve using bits	Number theory, cryptography
5	XOR Linked List	Doubly linked list that uses one pointer per node via XOR	Memory-constrained systems
6	Bitmask DP	Dynamic programming using bitmasks to represent states	Combinatorial problems
7	Fast Inverse Square Root	Famous bit hack from Quake III for fast 1/sqrt(x)	Game physics, graphics
8	Bit Twiddling Hacks	Collection of clever bit manipulation tricks	Performance optimization

Related Bit Manipulation Resources

Basic Programs

Interview Questions

MCQs

Advanced Tricks