[[Bitwise operations]]

Problem

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Brainstorming

Brute force

number_of_ones = 0
for i in range(32):
	if 13 >> i & 1 == 1:
		number_of_ones +=1

print(number_of_ones)	

• 🍅 (pomodoro::WORK) (duration:: 50m) (begin:: 2025-12-02 20:23) - (end:: 2025-12-02 21:13)

nums = 11
def decimal_to_binary(x:int):
	reversed_bits = []
	while x > 0:
		remainder = x % 2 
		reversed_bits.append(remainder)
		x  = x//2
	reversed_bits.reverse()
	return reversed_bits
print(decimal_to_binary(nums))

nums = 13
	
def count_bits(x:int):
	num_bits = 0
	while x:
		num_bits += x & 1
		x >>= 1
	return num_bits
	
print(decimal_to_binary(nums))
print(count_bits(nums))

while x:
means “while x is not zero,” not “not None.” The moment all bits have shifted away and x becomes 0, the loop ends.

Inside:

num_bits += x & 1
This checks the least significant bit (LSB). If that bit is 1, you increment the counter. Exactly right.

Then:

x >>= 1
This is a right shift,. The bits move to the right, drifting toward the LSB like sand in an hourglass.

Let’s use your example: x = 13 → binary 1101

Each iteration:

1. 1101
   LSB = 1 → count++
   Right shift → 0110

2. 0110
   LSB = 0
   Right shift → 0011

3. 0011
   LSB = 1
   Right shift → 0001

4. 0001
   LSB = 1
   Right shift → 0000

Loop ends.

Bit masking

⭐ What does x & 1 actually do?

Write any integer x in binary:

x = bₙ bₙ₋₁ … b₂ b₁ b₀

Now look at the number 1 in binary:

1 = 000…0001

When you compute:

x & 1

you’re doing a bitwise AND:

• AND returns 1 only if both bits are 1

• All the higher bits in 1 are zero

• So everything except the last bit is wiped out

So:

x & 1 → returns the least significant bit (LSB)

This gives you whether the number is odd or even:

• If LSB = 1 → number is odd

• If LSB = 0 → number is even

That’s why this expression is universally used for parity checks.

⭐ Why is this called “masking”?

Because the 1 in binary acts like a mask — a stencil that blocks everything except the bit you care about.

Think of a bit mask like a stencil in art:

• A mask with holes only in places you want to capture
• When you lay it over the original, only the allowed parts show through

So a mask:

000…0001

means:
“Hide all bits except the last one.”

This is why we say:

• x & 1 → mask out all bits except bit 0

• x & (1 << k) → mask out all bits except bit k

Masking = zeroing out what you don’t want, keeping only what you do want.

⭐ Intuition you can use forever

Masking is the bitwise equivalent of asking:

“Show me ONLY this specific bit from the entire number.”

x & 1 isolates the last bit.
x & 8 isolates the 2³ bit.
x & 0b11110000 isolates a whole chunk of bits.

Masking is a filter.

⭐ Why this works for odd/even checks?

Binary of an even number ends with 0.
Binary of an odd number ends with 1.

Example:

10 → 1010₂ → 1010 & 0001 = 0 11 → 1011₂ → 1011 & 0001 = 1

So x & 1 is basically nature’s built-in odd/even detector.

⭐ Visual example

Take x = 13

13 = 1101 1 = 0001 ----------- & = 0001 → which is 1

Take x = 12

12 = 1100 1 = 0001 ----------- & = 0000 → which is 0

Boom — parity found using a single CPU instruction.

⭐ Why masking is used everywhere (especially in DSA)

Because CPUs are happiest flipping bits.
Masking is:

• Extremely fast
• Zero-cost in terms of memory
• Perfect for checking flags, extracting bits, manipulating permissions, etc.

In DSA and low-level logic you see patterns like:

• x & (x - 1) → removes the lowest set bit
• x & -x → isolates the lowest set bit
• mask = (1 << k) → isolate bit k
• x & mask → check whether bit k is 1

Once you see the beauty, you never un see it.

• 🍅 (pomodoro::WORK) (duration:: 50m) (begin:: 2025-12-04 16:50) - (end:: 2025-12-04 17:40)

Optimised bit-fiddling trick

x & (x - 1) equals x with its lowest set bit erased.

Let’s test it with x = 16 (10000).

• x - 1 is 15, which is 01111 in binary.

• What is x & (x - 1)?

  10000 (16) & 01111 (15)

  00000

nums = 12

def count_bits(nums:int):
	counter = 0
	while nums>0:
		nums = nums & (nums-1)
		counter +=1
	return counter

print(count_bits(nums))

• 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-04 17:49) - (end:: 2025-12-04 18:09)

Let’s trace it with x = 12 (1100) to be certain.

Setup:

• count = 0
• x = 12

Iteration 1:

• while 12 > 0: (True)
• x = 12 & 11 -> x becomes 8 (1000).
• count becomes 1.

Iteration 2:

• while 8 > 0: (True)
• x = 8 & 7 -> x becomes 0 (0000).
• count becomes 2.

Iteration 3:

• while 0 > 0: (False). The loop terminates.

Result: The function returns count = 2. The number 12 (1100) has exactly two ‘1’ bits. The algorithm is correct.

This concludes our session on “Number of 1 Bits.”

Phase 5: The Reflection

1. We identified two primary algorithms. Can you describe the time complexity of each one? The first while x: loop, and this new while x > 0 with x & (x-1). Let n be the total number of bits in the integer type (e.g., 32 or 64) and k be the number of set bits.
2. Which algorithm is better if the input number is 2^30 - 1 (a long string of thirty ‘1’s)?
3. Which algorithm is better if the input number is 2^30 (a single ‘1’ followed by thirty ‘0’s)?
4. What was the key bitwise trick that unlocked the more efficient solution?