LeetCode & Algorithms Course
← Back to section

Pattern 5: Bit techniques

To close out the bits module, three techniques that combine what you've learned with other ideas: reusing counts (counting bits), reversing bits and summing without the + operator.

🎯

Try it first: Counting Bits

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Given an integer n, return an array ans of length n+1 where ans[i] is the number of 1 bits of i, for every i from 0 to n. Try to do it in O(n).

Example: n = 5 → [0, 1, 1, 2, 1, 2] (0,1,10,11,100,101).

Carregando editor…

Tried it? Counting the bits of each number separately works, but it's O(n · width). The theory below shows how to reuse already-computed answers and drop to O(n) — it's DP meeting bits.

Technique 1 — Counting Bits (reusing answers)

"For each i from 0 to n, how many 1 bits does it have?" Computing each one from scratch is wasteful: nearby numbers share bits. The insight (dynamic programming, which you'll see in depth in the last section):

The number i has the same bits as i >> 1 (i without its last bit), plus the last bit (i & 1).

That is, ans[i] = ans[i >> 1] + (i & 1). Since i >> 1 < i, the smaller answer has already been computed — just reuse it. Think of i = 13 (1101): dropping the last bit gives 110 (which is 6), and 6 has 2 bits; adding the last bit (1) gives 3.

Carregando editor…

Why O(n)? There are n numbers and each answer comes out in O(1) (a shift, an AND, an addition — all reusing something already done). Counting each number bit by bit would be O(n · width); reusing drops it to O(n).

Technique 2 — Reverse Bits (reverse the order of the bits)

"Reverse the 32 bits of a number." The idea: build the result bit by bit — pull the last bit of n and push it into res, which keeps getting shifted to the left. After 32 times, res is the mirror of n.

Carregando editor…

An important detail in JavaScript: use >>> (unsigned shift) and >>> 0 at the end, because JS's bitwise operators work on signed 32 bits — without this, the highest bit would be read as negative.

Technique 3 — Sum of Two Integers (sum without +)

"Add a and b without using + or -." It seems impossible, but binary addition is made of bits:

  • a ^ b sums the bits ignoring the carry.
  • (a & b) << 1 is exactly the carry: where both bits are 1, one carries over to the next place.

Repeat "sum without carry, then add the carry" until no carry is left — just like adding by hand, only in binary.

Carregando editor…

Notice the difference between the languages: JS operates natively on signed 32 bits, so the sum "just works". Python has integers of unbounded size, so we need to mask to 32 bits (& 0xFFFFFFFF) and rebuild the sign at the end — otherwise the carry would never finish for negative numbers. It's a great reminder that "the same algorithm" can require different care depending on how the language represents numbers.

🧠 Review quiz

0/4

1. In Counting Bits, why does ans[i] = ans[i >> 1] + (i & 1) work?

2. Why is Counting Bits O(n) and not O(n · width)?

3. In JavaScript, why does Reverse Bits use >>> and end with >>> 0?

4. In 'sum without +', what does (a & b) << 1 represent?

Summary

  • Counting Bits: ans[i] = ans[i>>1] + (i&1), reusing answers → O(n).
  • Reverse Bits: build the mirror bit by bit; in JS, watch out for signed 32 bits (>>>, >>> 0).
  • Sum without +: a^b sums without carry, (a&b)<<1 is the carry; repeat. In Python, mask to 32 bits.
  • The same bit algorithm can require different care per language.

Last stop: the synthesis of the Binary section and the quiz before the exam.

All lessons in this section