Counting Bits¶

Problem¶

Given an integer n, return an array of length n+1 where the i-th element is the number of 1-bits in the binary representation of i.

Approach¶

DP recurrence: dp[i] = dp[i >> 1] + (i & 1). The number of set bits in i equals the bits in i//2 plus whether the least significant bit is set.

When to Use¶

DP on binary representation — "count set bits for 0..n", "Hamming weight table". Recurrence dp[i] = dp[i>>1] + (i&1) builds on previously computed values. Also: popcount lookup tables.

Complexity¶


Time	`O(n)`
Space	`O(n)`

Implementation¶

SolutionTestsChallenge

counting_bits ¶

Counting Bits — count 1-bits for all numbers 0..n.

Problem

Given an integer n, return an array of length n+1 where the i-th element is the number of 1-bits in the binary representation of i.

Approach

DP recurrence: dp[i] = dp[i >> 1] + (i & 1). The number of set bits in i equals the bits in i//2 plus whether the least significant bit is set.

When to use

DP on binary representation — "count set bits for 0..n", "Hamming weight table". Recurrence dp[i] = dp[i>>1] + (i&1) builds on previously computed values. Also: popcount lookup tables.

Complexity

Time: O(n) Space: O(n)

counting_bits ¶

counting_bits(n: int) -> list[int]

Return a list of bit counts for 0..n.

counting_bits(5) [0, 1, 1, 2, 1, 2] counting_bits(0) [0]

Source code in src/algo/bit_manipulation/counting_bits.py

def counting_bits(n: int) -> list[int]:
    """Return a list of bit counts for 0..n.

    >>> counting_bits(5)
    [0, 1, 1, 2, 1, 2]
    >>> counting_bits(0)
    [0]
    """
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

tests/bit_manipulation/test_counting_bits.py

"""Tests for counting bits."""

from hypothesis import given
from hypothesis import strategies as st

from algo.bit_manipulation.counting_bits import counting_bits


class TestCountingBits:
    def test_zero(self) -> None:
        assert counting_bits(0) == [0]

    def test_five(self) -> None:
        assert counting_bits(5) == [0, 1, 1, 2, 1, 2]

    def test_two(self) -> None:
        assert counting_bits(2) == [0, 1, 1]

    def test_one(self) -> None:
        assert counting_bits(1) == [0, 1]

    def test_length(self) -> None:
        assert len(counting_bits(10)) == 11

    @given(n=st.integers(min_value=0, max_value=500))
    def test_matches_bin_count(self, n: int) -> None:
        result = counting_bits(n)
        for i in range(n + 1):
            assert result[i] == bin(i).count("1")

Implement it yourself

Run: just challenge bit_manipulation counting_bits

Then implement the functions to make all tests pass. Use just study bit_manipulation for watch mode.

Reveal Solution

counting_bits ¶

Counting Bits — count 1-bits for all numbers 0..n.

Problem

Given an integer n, return an array of length n+1 where the i-th element is the number of 1-bits in the binary representation of i.

Approach

DP recurrence: dp[i] = dp[i >> 1] + (i & 1). The number of set bits in i equals the bits in i//2 plus whether the least significant bit is set.

When to use

DP on binary representation — "count set bits for 0..n", "Hamming weight table". Recurrence dp[i] = dp[i>>1] + (i&1) builds on previously computed values. Also: popcount lookup tables.

Complexity

Time: O(n) Space: O(n)

counting_bits ¶

counting_bits(n: int) -> list[int]

Return a list of bit counts for 0..n.

counting_bits(5) [0, 1, 1, 2, 1, 2] counting_bits(0) [0]

Source code in src/algo/bit_manipulation/counting_bits.py

def counting_bits(n: int) -> list[int]:
    """Return a list of bit counts for 0..n.

    >>> counting_bits(5)
    [0, 1, 1, 2, 1, 2]
    >>> counting_bits(0)
    [0]
    """
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp