# Leetcode[1680] Concatenation of Consecutive Binary Numbers

Today, we will be looking at the following problem:

Given an integer

`n`

, returnthedecimal valueof the binary string formed by concatenating the binary representations of`1`

to`n`

in order,modulo`10^9 + 7`

.

Here is my solution:

In order to figure out this problem, I had to learn about bitwise operations and how shifting bits to the left is equal to multiplying the number by `2 * (number of places shifted)`

.

For example, if I had the number `25`

which translates to `11001`

. A left shift would result in `110010`

which is just a zero added to the end. As a result, you will get the number `50`

which is also `25 * 2`

.

Try doing the same with another number, let say `21568`

and bit shifting it by 2 places, you will get `86,272`

or `21568 * 2 * 2`

.

Now, we need to know how many places to shift the bits by for each number and that could be figured out by looping through the range of numbers and using the `&`

— bitwise AND operator. This operator returns `1`

only if the bit position of both numbers are `1`

.

For example, if we had the number `4`

in binary which is `100`

and `3`

in binary which is `11`

, the `&`

operator applied to the 2 numbers would result in `0`

. This is true for all numbers that correspond with a binary bit position. The decimal representation of a bit position with trailing zeros and the one minus that representation in binary will **always yield 0**.

As a result, we can loop through all the numbers starting from `1`

and when we find a number corresponds with a base 2 bit position with trailing zeros, we add to variable `pow2`

which counts the number of times a number has to be bit shifted to make way for the current number to be inserted into the sum.

Before the end of each loop, we shift the results by `Math.pow(2, pow2)`

and add the current number `i`

to fill in the zeroes that were added during the bit shifting. A modulo of 10⁹ + 7 is then applied. We apply the modulo during each loop to ensure that the number does not become too big to compute.

And there you have it, the solutions to Leetcode #1680 Concatenation of Consecutive Binary Numbers explained.