# [LeetCode 600. Non-negative Integers without Consecutive Ones ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/611/week-4-july-22nd-july-28th/3826/)
### Daily challenge Jul 25, 2021 (HARD)

>Given a positive integer `n`, return the number of the integers in the range ``[0, n]`` whose binary representations **do not** contain consecutive ones.

:::info
**Example 1:**
**Input:** n = 5
**Output:** 5
**Explanation:**
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.
:::

:::info
**Example 2:**
**Input:** n = 1
**Output:** 2
:::

:::info
**Example 3:**
**Input:** n = 2
**Output:** 3
:::

:::warning
**Constraints:**
1 <= n <= 10^9^
:::

---

### Approach 1 : Bit Manipulation :book:
**`0 ms ( 100% )`** **`O(32)`**

>以**二進位**觀察下列關係 :
**`[ 0 ~ 1 ) = 1`** ---> `( 0 )`。
**`[ 00 ~ 10 ) = 2`** ---> `( 00, 01 )`。
**`[ 000 ~ 100 ) = 3`** ---> `( 000, 001, 010 )`。
**`[ 0000 ~ 1000 ) = 5`** ---> `( 0000, 0001, 0010, 0100, 0101 )`。
**`[ 00000 ~ 10000 ) = 8`** ---> `( 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010 )`。
>...
>...

可以發現與 `Fibonacci Sequence` 相同。
假設 **`bit[k]`** 為 `Fibonacci Sequence` :
---> `bit[0] = 1` 表示**小於 ( 1 )~2~** 的總數。
---> `bit[1] = 2` 表示**小於 ( 10 )~2~** 的總數，以此類推。

因為 `input` 範圍屬於 `int`，所以 **`bit[]`** 只需要計算 32 項 ( or 30 項 ---> n <= 10^9^ )。

* **`k = 29`** 開始由大到小尋找 `n` 在哪幾項出現 `1`。
> 為什麼要從 `29` ?
> 因為 10^9^ = ( 111011100110101100101000000000)~2~ ---> `30 bit`。
* **`pre_bit`** 紀錄上一個 `bit` 是否為 `1`。
* 找到 `1` 後 **`ans += bit[k]`**。
>若 **`pre_bit == 1`** 表示之後的答案皆不符合題意，直接回傳 `ans` ( 原因在後面範例解釋 )。

---
>EXAMPLE : **`n = 150 = (10010110)`**。
>* `k = 7` ---> ans += bit[7] = 34。 [ **++00000000++** ~ **++10000000++** )。
>* `k = 4` ---> ans += bit[4] = 42。 [ 100 **++00000++** ~ 100 **++10000++** )。
>* `k = 2` ---> ans += bit[2] = 45。 [ 10010 **++000++** ~ 10010 **++100++** )。
>* `k = 1` ---> ans += bit[1] = 47。 [ 100101 **++00++** ~ 100101 **++10++** )。
此時 **`pre_bit == 1`** ---> 連續出現兩個 `1`，直接回傳 **`ans`**。
( 因為 10010 **++11++** 0...，都會出現連續兩個 `1` 的情況，所以不可再判斷。 )

:::success
:warning: 若 `n` 皆無出現連續兩個`1`的情況，回傳 **`ans + 1`**，因為 `n` 本身也是一個答案。
:::

class Solution {
public:
    int findIntegers(int n) {
        int bit[32];
        bit[0] = 1;
        bit[1] = 2;
        for(int i=2; i<32; i++){
            bit[i] = bit[i-1] + bit[i-2];
        }
        
        int k = 29;
        int pre_bit = 0;
        int ans = 0;
        
        while(k >= 0){
            if(n & (1<<k)){
                ans += bit[k];
                if(pre_bit == 1)    return ans;
                pre_bit = 1;
            }
            else    pre_bit = 0;
            
            k--;
        }

        return ans + 1;
    }
};