These are my notes of Neetcodes' awesome video on Bit Manipulation. I am going to try my best to express his ideas in my own words for the reader to understand and for me to practice expressing complex ideas in simpler terms using markdown.

What is Bit Manipulation?

What is a Bit?

As we all know, all code and operations are essentially 1s and 0s. These 1s and 0s are called Bits. These bits make up collectively, the modern computing system.

How to manipulate bits?

There are several operations that we can do to manipulate bits. It is essentially these operations that happen at the lowest level of computing. Some of these operations that we usually applying while coding and problem solving are:

AND Operation (&)

Both bits have to be 1 for the result to be 1. Else result is 0.

OR Operation (|)

Either of the bits have to be 1 for the result to be 1. Else result is 0.

XOR Operation (^)

Only one bit has to be 1 for the result to be 1. Else result is 0.

Negation Operation (~)

Returns the opposite of the given bit.

Bit Shifting (<< or >>)

Most programming languages have 32 bit integers. In binary form, we can shift all the bits to the right or left.

For example, lets assume that instead of 32, we have an integer with just 3 bits: n = 001 Applying a left shift by 1 here, n = n << 1 we get 010 Doing the same again, we get 100 But doing it again, we get 000. This was because we assumed the integer to have only 3 bits.

What I wanted to point out by the above exercise is that bits don't get carried away like in addition when we do bit shifting.

Looking at the big picture,

Let's say we have a decimal integer 145, Here,

5 is in 1's place,    1*10^0
4 is in 10's place,   1*10^1
1 is in 100's place.  1*10^2

As we can see, this is the basics of the Base10 system.

Similarly, Let's say we have a `binary integer 110, Here,

0 is in 1's place,   1*2^0
1 is in 2's place,   1*2^1
1 is in 4's place.   1*2^2

We notice that Base2 system has multiples of 2.

Coming back to shifting, when we do a left shift, what we really do is move the position of each bit to the next binary place, and with a right shift, we move one place back. In simple terms,

• left shift a number -> multiply by 2
• right shift a number -> divide by 2

And if we really think about it, lets say we had to do a decimal shift instead of a binary shift, we can do this easily by multiplying or dividing by 10. Eg.

n = 145
Decimal left shift this by 1 place,
145 * 10 = 1450
Haa! All the digits shifted to one place left.

An example for right shift

100 is 4 in binary,
100 >> 1 = 010 which is 2 in binary
010 >> 1 = 001 which is 1 in binary

As we can see, right shift ends up doing a division by 2.

Note: Python has unlimited bits for its integers instead of a fixed 32

Code

python
# AND
n = 1 & 1
# OR
n = 1 | 0
# XOR (Exclusive OR)
## If 1 is present, we get 1. Else we get 0.
n = 0 ^ 1 
# NOT (negation)
n = ~n
# Bit shifting (Look at the direction of the Arrows)
n = 1
n = n << 1 # Left shift
n = n >> 1 # Right shift

Extras

**Note: Doing AND with 1 and any X number, will result in 1 or 0. We can check odd or even numbers by this logic as all even numbers have the last bit as 0.

---

Checking if a Number Is a Power of Two

There is a very common bit manipulation check you will see in problems and interviews:

python
n > 0 and (n & (n - 1)) == 0

At first glance, this looks confusing. Let’s break it down from first principles.

---

How powers of two look in binary

A number is a power of two if it has exactly one 1 bit in its binary representation.

Examples:

1  -> 1
2  -> 10
4  -> 100
8  -> 1000
16 -> 10000

Every power of two follows the same pattern:

• one 1
• all remaining bits are 0

This single observation is the key.

---

What does n - 1 do in binary?

Subtracting 1 from a number in binary has a predictable effect.

If n is a power of two:

n     = 1000
n - 1 = 0111

What happened?

• the single 1 became 0
• all bits to the right turned into 1

This always happens for powers of two.

If n is not a power of two:

n     = 1010
n - 1 = 1001

Here, multiple 1s already exist, so subtracting 1 does not wipe everything clean.

---

Why does n & (n - 1) work?

The AND (&) operator keeps a bit only if both sides have 1 in that position.

Power of two case

n     = 1000
n - 1 = 0111
----------------
AND   = 0000

There are no overlapping 1s. The result is 0.

Not a power of two case

bash
n     = 1010
n - 1 = 1001
----------------
AND   = 1000

At least one 1 survives. The result is not 0.

Why do we check n > 0?

Without it:

python
0 & (0 - 1) = 0 & -1 = 0

This would incorrectly classify 0 as a power of two. So we explicitly exclude it.

---

Final intuition to remember

n & (n - 1) removes the lowest set bit from n

• If removing that bit makes the number 0, there was only one 1 to begin with.
• That means the number was a power of two.

---

Final check

python
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0