Bitwise Operators in JavaScript

Bitwise Operators and Manipulation

Welcome to the world of Bit Manipulation. This is the act of algorithmically manipulating bits or other pieces of data shorter than a word. It's a powerful technique for saving space, increasing speed, and solving certain problems elegantly.

---

1. The Core Bitwise Operators

JavaScript's bitwise operators work on 32-bit signed integers. They are:

• AND (&): Returns a 1 in each bit position for which the corresponding bits of both operands are 1s.
• OR (|): Returns a 1 in each bit position for which the corresponding bits of either or both operands are 1s.
• XOR (^): Returns a 1 in each bit position for which the corresponding bits of either but not both operands are 1s.
• NOT (~): Inverts the bits of its operand.
• Left Shift (<<): Shifts the first operand the specified number of bits to the left. Excess bits shifted off to the left are discarded. Zero bits are shifted in from the right.
• Sign-propagating Right Shift (>>): Shifts the first operand the specified number of bits to the right. Excess bits shifted off to the right are discarded. Copies of the leftmost bit are shifted in from the left.
• Zero-fill Right Shift (>>>): Shifts the first operand the specified number of bits to the right. Excess bits shifted off to the right are discarded. Zero bits are shifted in from the left.

---

2. Common Bitmasking Operations

A "bitmask" is a value used with bitwise operations to set, clear, or toggle specific bits of another value.

• Set a Bit: To set the k-th bit of a number n, we use n | (1 << k).
• Clear a Bit: To clear the k-th bit, we use n & ~(1 << k).
• Toggle a Bit: To toggle the k-th bit, we use n ^ (1 << k).
• Test a Bit: To check if the k-th bit is set, we use (n >> k) & 1.

function setBit(n, k) { return n | (1 << k); }
function clearBit(n, k) { return n & ~(1 << k); }
function toggleBit(n, k) { return n ^ (1 << k); }
function testBit(n, k) { return ((n >> k) & 1) === 1; }

---

3. Practical Applications and Tricks

• Flags and Masks: A single integer can represent a set of boolean flags, saving space. Each bit corresponds to a flag.

• Power of Two Check: A number n is a power of two if (n > 0) && ((n & (n - 1)) === 0).

• Fast Arithmetic: In the past, bit shifts were used for fast multiplication and division by powers of two. Modern compilers often do this optimization automatically.

• Iterating Submasks: A common pattern in competitive programming is to iterate through all the submasks of a given mask:

  for (let submask = mask; submask > 0; submask = (submask - 1) & mask) {
    // process submask
  }
  

---

Key Takeaway: Bit manipulation provides a low-level way to work with data, offering performance and space benefits. Understanding bitwise operators and masking techniques is essential for certain types of problems, especially in systems programming, competitive programming, and graphics.