Go | Bit manipulation
Let\'s say n = 3. To concatenate numbers 1, 2, 3 (binary: 1, 10, 11), we do the following:\n1. Add 1 to the result; ans = 1\n2. Move the result two bits left to
Let\'s say `n = 3`. To concatenate numbers 1, 2, 3 (binary: `1`, `10`, `11`), we do the following:\n1. Add `1` to the result; `ans = 1`\n2. Move the result two bits left to make a space for the next number; `ans = 100`\n3. Add `10`; `ans = 110`\n4. Move the result two more bits left; `ans = 11000`\n5. Add `11`; `ans = 11011`.\n \nTo understand, how much do we need to move `ans` to the left, we create variable `power`, which is incremented every time when `i` is increased twice.\n\n```\nfunc concatenatedBinary(n int) int {\n    ans := 0\n    threshold := 1\n    power := 0\n    for i := 1; i <= n; i++ {\n        if i >= threshold {\n            threshold = threshold << 1\n            power += 1            \n        }\n        ans = (ans << power + i) % 1000000007\n    }\n    return ans\n}\n```
['Bit Manipulation', 'Go']