Bit Manipulation

A comprehensive guide to bit manipulation, its operations, and use cases in computing.

What is Bit Manipulation?

Bit manipulation refers to the process of directly handling individual bits of a number using bitwise operations. It is a crucial concept in computing, optimizing performance in tasks like encryption, compression, and low-level programming.

Why is Bit Manipulation Important?

• Fast Operations: Bitwise operations are much faster than arithmetic operations.
• Memory Efficiency: Used in data compression and storage optimization.
• Low-Level System Programming: Essential for working with hardware, microcontrollers, and embedded systems.
• Algorithm Optimization: Used in fast calculations, cryptography, and data structures like bitsets and Bloom filters.

Bitwise Operators

Bit manipulation primarily involves six operators:

Operator	Symbol	Description
AND	&	Sets a bit if both corresponding bits are 1
OR	`	Sets a bit if at least one corresponding bit is 1
XOR	^	Sets a bit if only one corresponding bit is 1
NOT	~	Inverts all bits (bitwise complement)
Left Shift	<<	Shifts bits to the left, multiplying by 2^n
Right Shift	>>	Shifts bits to the right, dividing by 2^n

1. Bitwise AND (&)

let a = 5; // 0101 (binary)
let b = 3; // 0011 (binary)
console.log(a & b); // 0001 (1 in decimal)

2. Bitwise OR (|)

let a = 5; // 0101
let b = 3; // 0011
console.log(a | b); // 0111 (7 in decimal)

3. Bitwise XOR (^)

let a = 5; // 0101
let b = 3; // 0011
console.log(a ^ b); // 0110 (6 in decimal)

4. Bitwise NOT (~)

let a = 5; // 00000101 (8-bit representation)
console.log(~a); // 11111010 (-6 in decimal due to two's complement)

5. Left Shift (<<)

let a = 5; // 0101
console.log(a << 1); // 1010 (10 in decimal)

6. Right Shift (>>)

let a = 5; // 0101
console.log(a >> 1); // 0010 (2 in decimal)

Common Bit Manipulation Tricks

1. Checking if a Number is Even or Odd

function isEven(n) {
  return (n & 1) === 0;
}

console.log(isEven(4)); // true
console.log(isEven(7)); // false

2. Checking if a Number is a Power of 2

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

console.log(isPowerOfTwo(8)); // true
console.log(isPowerOfTwo(10)); // false

3. Swapping Two Numbers Without a Temporary Variable

let x = 5,
  y = 3;
x = x ^ y;
y = x ^ y;
x = x ^ y;
console.log(x, y); // 3, 5

4. Counting Set Bits in a Number (Brian Kernighan’s Algorithm)

function countSetBits(n) {
  let count = 0;
  while (n > 0) {
    n &= n - 1;
    count++;
  }
  return count;
}

console.log(countSetBits(9)); // 2 (1001 has 2 set bits)

Applications of Bit Manipulation

• Data Compression (Huffman Encoding)
• Cryptography (Encryption & Decryption)
• Graphics Rendering (Efficient pixel manipulation)
• Networking (Bit masking in IP addressing)
• Embedded Systems (Working with hardware registers)

Summary

Bit manipulation is a powerful tool in computing, enabling efficient data processing, fast algorithms, and low-level programming. Mastering bitwise operations can significantly improve your problem-solving skills in competitive programming, system programming, and embedded development.