leetcode 1680. Concatenation of Consecutive Binary Numbers(连接连续的二进制数)
Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 109 + 7.
Example 1:
Input: n = 1
Output: 1
Explanation: “1” in binary corresponds to the decimal value 1.
Example 2:
Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to “1”, “10”, and “11”.
After concatenating them, we have “11011”, which corresponds to the decimal value 27.
把1~n的二进制数从左到右连接起来(像字符串连接那样),拼成的十进制数是多少(取模后)。
mod = 109+7
思路:
这是一个二进制数操作的问题。
首先是把1~n转为二进制数,然后像字符串连接那样连接它们,然后转为十进制数,每转一个数取一次模。
问题就出在1~n怎么转成二进制数,怎么连接,怎么再转为十进制数。
其实最终反正是十进制数,那直接把1~n的十进制数相加不就好了,
问题是每相加一次需要向左移位,才能加下一个。
那么要移多少位呢?
比如2 是10,需要左移2位,4是100,需要左移3位。
怎么计算需要移的位数?
两种方法:
一是用以2为底的log计算,比如log(2)=1,需要左移log(2)+1位,
4也是一样,左移log(4)+1=3位。
二是利用2的幂一定满足 i & (i-1) = 0这个条件,每满足一次,bit位+1,
比如2, 先是1 & (1-0) =0, bit=1, 然后2&(2-1)=0,bit++变为2, 4&(4-1)=0, bit++变为3
所以,思考的关键在于将二进制数的拼接和转十进制数的问题 转化为左移bit位之后再直接加十进制数。
用log计算左移位数:
public int concatenatedBinary(int n) {
long res = 0;
int mod = 1000000007;
for(int i = 1; i <= n; i++) {
int bitCnt = (int)(Math.log(i) / Math.log(2)) + 1;
res = (((res << bitCnt) % mod) + i) % mod;
}
return (int)res;
}
用 i & (i-1) 计算bit位数:
public int concatenatedBinary(int n) {
long res = 0;
int mod = 1000000007;
int bitCnt = 0;
for(int i = 1; i <= n; i++) {
if((i & (i-1)) == 0) bitCnt ++;
res = (((res << bitCnt) % mod) + i) % mod;
}
return (int)res;
}