C++ O(N) time iterative
See my latest update in repo LeetCode\n\n## Solution 1. \n\nLet f(n) be the answer. sum_len(a, b) = sum( len(i) | a <= i <= b) and len(i) is the number of bits 
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. \n\nLet `f(n)` be the answer. `sum_len(a, b) = sum( len(i) | a <= i <= b)` and `len(i)` is the number of bits in `i`.\n\nFor example: `len(1) = 1`, `len(3) = 2`, `len(6) = 3`. `sum_len(1,4) = len(1) + len(2) + len(3) + len(4) = 1 + 2 + 2 + 3 = 8`.\n\nSo we have\n\n```plaintext\nf(n)   = (1 << sum_len(2, n))   + (2 << sum_len(3, n))   + ... + ((n - 1) << sum_len(n, n)) + (n << 0)\n\n// Example: f(4) = 11011100 = (1 << (2+2+3)) + (2 << (2+3)) + (3 << 3) + (4 << 0)\n\nf(n-1) = (1 << sum_len(2, n-1)) + (2 << sum_len(3, n-1)) + ... + ((n - 1) << 0)\n\nf(n) = (f(n-1) << len(n)) + n\n```\n\nSince `f(0) = 0`, we can iteratively build `f(n)`.\n\n```plaintext\nf(0) = 0\nf(1) = 1     = (f(0) << 1) + 1  // len(1) = 1\nf(2) = 110   = (f(1) << 2) + 2  // len(2) = 2\nf(3) = 11011 = (f(2) << 2) + 3  // len(3) = 2\n...\n```\n\n```cpp\n// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/\n// Author: github.com/lzl124631x\n// Time: O(NlogN)\n// Space: O(1)\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        long ans = 0, mod = 1e9+7;\n        for (int i = 1; i <= n; ++i) {\n            int len = 0;\n            for (int j = i; j; j >>= 1, ++len);\n            ans = ((ans << len) % mod + i) % mod;\n        }\n        return ans;\n    }\n};\n```\n\n## Solution 2.\n\nWe spent `O(logN)` time for calculating the `len`. We can reduce it to `O(1)` with the help of `__builtin_clz` which returns the number of leading zeros for a number, so `len = 32 - __builtin_clz(i)`. (Thanks 0xFFFFFFFF)\n\n```cpp\n// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        long ans = 0, mod = 1e9+7;\n        for (int i = 1; i <= n; ++i) ans = ((ans << (32 - __builtin_clz(i))) % mod + i) % mod;\n        return ans;\n    }\n};\n```\n\nOr, with the observation that the `len` only increment when the `i` is a power of `2`, we can increment `len` only when `i` has a single bit `1`. We can check this via `(i & (i - 1)) == 0`. (Thanks @LVL99)\n\n```cpp\n// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\nclass Solution {\npublic:\n    int concatenatedBinary(int n) {\n        long ans = 0, mod = 1e9+7, len = 0;\n        for (int i = 1; i <= n; ++i) {\n            if ((i & (i - 1)) == 0) ++len;\n            ans = ((ans << len) % mod + i) % mod;\n        }\n        return ans;\n    }\n};\n```
[]