Concatenation of Consecutive Binary Numbers: Bit Shifting Patterns

Given an integer n, concatenate the binary representations of 1 to n in order, interpret the result as a single binary number, and return that number modulo 10^9 + 7. For example, when n = 3, you concatenate "1", "10", and "11" to get "11011", which is 27 in decimal.

This is LeetCode 1680: Concatenation of Consecutive Binary Numbers, and it is a clean exercise in bit shifting and modular arithmetic.

Why this problem matters

Concatenation of Consecutive Binary Numbers teaches you to think about binary representation at a mechanical level. Instead of treating binary as an abstract concept, you physically simulate what it means to "paste" one binary string after another. The key operations, left shifting and bitwise OR, are the same primitives that show up in encoding schemes, hash functions, and low-level data packing.

This problem also reinforces modular arithmetic under repeated multiplication and addition. You cannot store the full concatenated number (it grows exponentially), so you need to apply the modulus at every step. Learning to weave % MOD into shift-and-add logic is a skill that transfers to many other problems involving large numbers.

The key insight

To concatenate binary representations, you do not need to build an actual string. Instead, you can simulate the concatenation numerically. When you append the binary of number i to the running result, you are doing two things:

1. Shift the result left by the number of bits in i, making room for the new digits.
2. OR (or add) i into the newly created space.

The number of bits in i is i.bit_length() in Python, which returns the position of the highest set bit. For example, 3 in binary is "11", so bit_length() returns 2. You shift the result left by 2 positions and then OR in 3.

The solution

def concatenated_binary(n: int) -> int:
    MOD = 10**9 + 7
    result = 0

    for i in range(1, n + 1):
        bits = i.bit_length()
        result = ((result << bits) | i) % MOD

    return result

We iterate from 1 to n. For each number i, we compute its bit length, left-shift the running result by that many positions, OR in i, and take the modulus. The final value of result is the answer.

The shift-and-OR operation is equivalent to string concatenation in binary. If result currently represents the binary string "110" and you want to append "11" (the number 3), you shift left by 2 to get "11000", then OR with "11" to get "11011". This is exactly what concatenation does, but without ever building a string.

Visual walkthrough

Each step follows the same pattern: compute the bit length of the current number, shift the accumulated result left by that many bits, and OR in the current number. The modulus keeps the result manageable. By the end, result holds the decimal value of the full concatenated binary string.

Complexity analysis

Time: We loop through numbers 1 to n exactly once. Each iteration does a constant amount of work: one bit_length() call, one left shift, one OR, and one modulus. Total: O(n).

Space: We use a single integer result and a loop variable. No arrays, no strings, no extra data structures. Total: O(1).

The building blocks

1. Bit length of a number

The bit length tells you how many binary digits a number has. This is the foundation of the shift amount. You can compute it with bit_length() in Python, or by finding the position of the most significant bit. There is also a useful pattern: the bit length increases by 1 each time i is a power of 2.

bits = i.bit_length()

2. Left shift and OR for binary concatenation

Left shifting by k positions multiplies a number by 2^k, which is equivalent to appending k zero bits on the right. Then OR-ing in a k-bit number fills those zeros with the desired bits. Together, these two operations simulate binary string concatenation without any string operations.

result = (result << bits) | i

Edge cases

• n = 1: The binary of 1 is "1", so the answer is 1. The loop runs once, shifts 0 left by 1 bit to get 0, and ORs in 1.
• Large n: The result grows extremely fast without the modulus. With n = 100000, the concatenated binary would have hundreds of thousands of digits. The % MOD at every step keeps the value within bounds.
• Powers of 2: When i is a power of 2, its bit length increases by 1 compared to i - 1. The algorithm handles this naturally because bit_length() returns the correct value for every i.
• n = 2: Binary is "1" + "10" = "110" = 6. A good sanity check for your implementation.

From understanding to recall

You have seen how bit length, left shift, and OR combine to simulate binary concatenation. The logic is compact: three operations inside a loop. But under interview pressure, the details matter. Which direction do you shift? Do you OR or add? Where does the modulus go?

Spaced repetition locks in these details. You practice writing the loop from scratch, computing the bit length, applying the shift, and placing the modulus correctly. After a few rounds, the pattern becomes automatic. You do not need to re-derive it from first principles.

Related posts

• Reverse Bits - Bit-by-bit construction of a result through shifting, the same mechanical pattern used here in reverse
• Number of 1 Bits - Counting set bits with bitwise AND, another fundamental bit manipulation primitive
• Counting Bits - Computing bit counts for a range of numbers, combining bit operations with dynamic programming

CodeBricks breaks Concatenation of Consecutive Binary Numbers into its bit-length, shift, and OR building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a bit manipulation problem shows up in your interview, you do not hesitate. You just write it.