Bit Manipulation Basics

Concept

Underneath the high-level abstractions of React, Python, and Java, computers only understand one thing: Electricity.
A wire either has current (1) or it doesn’t (0).

These are Bits (Binary Digits). Everything in computer science is built on bits.
Bit Manipulation is the art of bypassing high-level math (like addition, multiplication, or modulo) and manipulating these raw 1s and 0s directly in the CPU’s Arithmetic Logic Unit (ALU).

Bitwise operations are the absolute fastest operations a computer can perform. They execute in a single clock cycle.

Binary Representation

Humans count in Base-10 (Decimal). We have 10 digits (0-9). When we run out of digits, we add a new column to the left: 1s, 10s, 100s, 1000s.

Computers count in Base-2 (Binary). They only have 2 digits (0 and 1).
When they run out of digits, they add a new column. But instead of multiplying by 10, the columns multiply by 2!
Columns: 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1

Let’s write the number 13 in Binary using 8 bits (a Byte):

• Does 13 have an 8? Yes! (Remainder 5).
• Does 5 have a 4? Yes! (Remainder 1).
• Does 1 have a 2? No.
• Does 1 have a 1? Yes!
  Binary for 13: 0 0 0 0 1 1 0 1

Two’s Complement (Negative Numbers)

How does a computer represent a negative number like -13 if it only has 1s and 0s?
It uses a brilliant mathematical hack called Two’s Complement.

The absolute left-most bit in the integer (the Most Significant Bit, or MSB) is hijacked. It becomes the Sign Bit.

• If the MSB is 0, the number is Positive.
• If the MSB is 1, the number is Negative.

How to convert 13 into -13:

1. Start with the positive binary: 0000 1101 (13)
2. Invert every single bit (One’s Complement): 1111 0010
3. Add 1 to the result: 1111 0011

1111 0011 is the official computer representation of -13.
Why do we add 1? If we just inverted the bits, the binary 0000 0000 (Zero) would invert to 1111 1111 (Negative Zero). “Negative Zero” is mathematically illegal and breaks the ALU. By adding 1, it magically shifts the entire negative spectrum over, perfectly eliminating Negative Zero and allowing standard binary addition to work flawlessly with negative numbers!

Interview Strategy

You will rarely be asked to convert Binary to Decimal in a FAANG interview.
Instead, Bit Manipulation is used as an $O(1)$ Space optimization trick to replace Hash Sets, or as an $O(1)$ Time optimization trick to replace division/modulo.

The Golden Rules of Bits:

• X & 1 checks if a number is Odd or Even.
• X >> 1 mathematically divides a number by 2.
• X << 1 mathematically multiplies a number by 2.
• X ^ X (XOR against itself) always mathematically cancels out to 0.

Interview Questions

Q: A 32-bit Signed Integer can hold a maximum value of 2,147,483,647. What happens if you add 1 to it?
A: This causes an Integer Overflow. The binary of 2,147,483,647 is 0111...1111. If you add 1, it ripples all the way to the left, flipping the Sign Bit to 1, and turning the rest into 0s: 1000...0000. Because the Sign Bit is now 1, the computer reads this as a massive negative number. The value wraps around to -2,147,483,648.

Q: In JavaScript, what happens if you try to perform Bitwise operations on a massive number like 9 Quadrillion?
A: It breaks. JavaScript numbers are 64-bit IEEE-754 Floats. However, the moment you use a bitwise operator (&, |, >>), V8 forcefully truncates the number into a 32-bit Signed Integer before performing the operation. Any value larger than 2.14 Billion will be violently truncated and corrupted. You must use the modern BigInt type to perform bitwise operations on massive numbers in JS.