AND, OR, XOR

Concept

Bitwise operators perform mathematical logic on a bit-by-bit basis. They take two numbers, line up their binary columns perfectly, and execute a logical gate down the column.

1. Bitwise AND (&)

The AND gate requires BOTH bits to be 1 to output a 1. Otherwise, it outputs 0.

  1 0 1 1  (11)
& 1 1 0 0  (12)
---------
  1 0 0 0  (8)

Primary Use Case (Masking): AND is used to “mask” (hide) bits. If you want to check if a specific bit is a 1, you AND it with a mask of 1.

• X & 1: Checks if a number is Odd. (Odd numbers always have a 1 in the absolute right-most 1s column. Even numbers have a 0. ANDing with 1 instantly isolates that column).

2. Bitwise OR (|)

The OR gate requires AT LEAST ONE bit to be 1 to output a 1.

  1 0 1 1  (11)
| 1 1 0 0  (12)
---------
  1 1 1 1  (15)

Primary Use Case (Setting): OR is used to forcefully turn a bit ON. If you OR a bit with 1, it becomes 1. If you OR it with 0, it stays whatever it originally was.

3. Bitwise XOR (^) (Exclusive OR)

The XOR gate requires the bits to be DIFFERENT to output a 1. If they are the same (both 1 or both 0), it outputs 0.

  1 0 1 1  (11)
^ 1 1 0 0  (12)
---------
  0 1 1 1  (7)

Primary Use Case (Toggling / Canceling): XOR is the most tested bitwise operator in FAANG interviews because of its magical mathematical properties:

1. X ^ 0 = X (XORing with 0 changes nothing).
2. X ^ 1 = ~X (XORing with 1 flips the bit).
3. X ^ X = 0 (XORing a number against ITSELF perfectly cancels it out to Zero!).

4. Bitwise NOT (~)

The NOT gate takes a single number and simply flips every single 1 to 0, and 0 to 1.
Because it flips the Sign Bit as well, ~X mathematically equals -(X + 1).
~5 evaluates to -6.

Bitmasking (Using Bits as Arrays)

Imagine you need to track which English letters (‘a’ to ‘z’) you have seen so far in a string.
You would normally use a Hash Set (Set<string>) or a boolean array of length 26. This takes $O(N)$ Space.

Because there are only 26 letters in the alphabet, and an Integer has 32 bits, you can use a single 32-bit Integer as a perfectly functional Hash Set! This drops the Space Complexity to pure $O(1)$.

// The "Hash Set" is just a single Integer variable (Starts as 000...000)
let seenLetters = 0; 

// 1. Calculate the letter's index (0 to 25)
const charCode = 'c'.charCodeAt(0) - 'a'.charCodeAt(0); // 'c' is index 2

// 2. Create a "Mask" by shifting a 1 into that specific column!
// 1 << 2 creates the binary: 000...000100
const mask = 1 << charCode;

// 3. To "ADD" the letter to our Set, we use OR (|)
seenLetters = seenLetters | mask; 

// 4. To "CHECK" if the letter is in our Set, we use AND (&)
if ((seenLetters & mask) !== 0) {
    console.log("We have seen 'c' before!");
}

Interview Questions

Q: In JavaScript, what is the difference between && and &?
A: && is the Logical AND operator. It evaluates the “truthiness” of entire variables. true && false is false. It relies on Short-Circuit evaluation (if the left side is false, it aborts immediately).
& is the Bitwise AND operator. It evaluates the strict mathematical binary bits of two integers column by column. It does not short-circuit.

Q: How do you mathematically “Turn Off” a specific bit without touching the other bits?
A: You use an AND gate with an inverted mask! If you want to turn off the 3rd bit, you create a mask with a 1 in the 3rd column (mask = 1 << 3 -> 00001000). You invert the mask using NOT (~mask -> 11110111). You then AND it with the original number (X & ~mask). Every column that aligns with a 1 remains unchanged, but the 3rd column aligns with the 0 and is permanently wiped out!