# [1680. Concatenation of Consecutive Binary Numbers (M) ***MWChang***](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/)
###### tags: `leetcode` `bit manipulation`

## 思路
注意題目有要求 $modulo\ 10^9+7$，因此每圈要取餘數控制整體空間。
流程為從 $1$ 開始，把 res 左移(<<)並利用 OR(|) 運算把二進制的值加進去:

1. res 左移1位，插入1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res = [1] = $(1)_{10}$
2. res 左移2位，插入10 &nbsp;&nbsp;&nbsp;res = [110] = $(5)_{10}$
3. res 左移2位，插入11 &nbsp;&nbsp;&nbsp;res = [11011] = $(27)_{10}$
4. res 左移3位，插入100 &nbsp;res = [111011100] = $(?)_{10}$

**hint**
- 找出何時進來的值需要多進一位(binary)。
- 當數字`i`為二的次方數，那轉成二進制會變成`1000000...`，與`i-1`的二進制做`AND(&)`運算將會為0，因此用此方法確認`len`是否需要+1。

## Code

int concatenatedBinary(int n){
    const int M = 1e9 + 7; /* for the modulo */
    long res = 0; /* result, long type incase int(32bits) can't handle it */
    int len = 0; /* counter (in bits) for the result to move left */

    for(int i = 1; i <= n; ++i){
        if( (i & (i-1)) == 0) /* compare with (i - 1) to check if i carries in binary */
            ++len;
        res = ( i | (res << len) ) % M; /* move left and use AND to plant i into res */
    }
    return res;
}

## Comment
***Tjuvaquan***
你的筆記可以再亂一點沒關係，整理過ㄌ
***MWChang***
好強，牛皮