###### tags: `leetcode` `Medium` `Math` `Bit Manipulation` `Simulation`
# [1680.Concatenation Of Consecutive Binary Numbers](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/)

## Description

Given an integer `n`, return the **decimal value** of the binary string formed by concatenating the binary representations of `1` to `n` in order, **modulo** $10^9 + 7$.

## Examples

### Example 1:

**Input**: n = 1
**Output**: 1
**Explanation**: "1" in binary corresponds to the decimal value 1.

### Example 2:

**Input**: n = 3
**Output**: 27
**Explanation**: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

### Example 3:

**Input**: n = 12
**Output**: 505379714
**Explanation**: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo $10^9 + 7$, the result is 505379714.

## Constraints:

- $1\leq n\leq 10^5$

## Code

int concatenatedBinary(int n) {
    int mod = 1e9 + 7;
    long ans = 0;
    int size = 0;
    for (int i = 1; i <= n; i++) {
        if ((i & (i - 1)) == 0)
            size++;
        ans <<= size;
        ans |= i;
        ans %= mod;
    }
    return ans;
}

## Complexity

|Space |Time |
|- |- |
|$O(1)$|$O(n)$|

## Result

- Runtime: 31 ms, 75 %
- Memory: 5.3 MB, 100 %

## Notes

### How to get bit-size of numbers

- Method 1

int GetBitSize(int number){
    temp = number;
    count=0;
    while(temp!=0){
        temp = temp>>1;
        count++;
    }
    return count;
}

Directly count number length during each turn shifting number right 1 bit.
Its complexity is

|Space |Time |
|- |- |
|$O(1)$|$O(log(n))$|

- Method 2

int GetBitSize(int number){
    int count = 0;
    for(int i = 1 ; i <= number ; i++){
        if ((i & (i - 1)) == 0)
            count++;
    }
    return count;
}

Just like Kernighan's Algorithm. Kernighan's Algorithm wants to count how many set bit in a given number.
It uses the feature that `AND` operation of `number` and `number - 1` will set the less significant setting bit. Like

|Number |Binary|
|- |- |
|N = 12 |`1100`|
|N-1 = 11 |`1011`|
|N & (N-1) = 8 |`1000`|

After then, setting new `number` as `number & (number - 1)`, until the number become zero.
If we inverse this operation, we can find the length of binary increase as the number carries.
It is like the behavir of less significant setting bit works, only become zero as it carry(`10...0` & `01...1`)

|Number |Binary|
|- |- |
|N = 8 |`1000`|
|N-1 = 7 |`0111`|
|N & (N-1) = 0 |`0000`|

Its complexity is

|Space |Time |
|- |- |
|$O(1)$|$O(n)$|