1680. 连接连续二进制数字Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 109 + 7 取余的结果。
示例 1：
输入：n = 1
输出：1
解释：二进制的 "1" 对应着十进制的 1 。
示例 2：
输入：n = 3
输出：27
解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。
将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。
示例 3：
输入：n = 12
输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 109 + 7 取余后，结果为 505379714 。
提示：
- 1 <= n <= 105
# 思路
利用位运算
# 解法
class Solution {
public int concatenatedBinary(int n) {
final int MOD = 1000000000 + 7;
long ans = 0; //long避免溢出
int bit = 0;//需要移动的位数
for(int i = 1; i <= n; ++i) {
//当i是2的n次方时，i & (i - 1) == 0 如： i = 4, 二进制i为100, i - 1 = 011， i & (i - 1) == 0
if((i & (i - 1)) == 0){
++bit;
}
ans = ((ans << bit) + i) % MOD;
}
return (int)ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 总结
- 分析出几种情况，然后分别对各个情况实现
