b_lc_连接连续二进制数字（连接相当于左移然后异或）

给你一个整数 n(1<=1e5)，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 10^9+7 取余的结果。

思路：暴力

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        ans=''
        mod=int(1e9+7)
        for i in range(n+1):
            ans=ans+bin(int(i)%mod)[2:]
        return int(ans,2)%mod

二进制思路：二进制数a、b的连接相当于a左移(cnt_2(b))位，在异或上b，公式为：x=(x<<cnt(i))+i)，而只有i是2的次幂数，左移的位数才会增加1，否则它会以当前最大2的次幂数的位数为基准

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        x,k,mod=0,0,int(1e9+7)
        for i in range(1,n+1):
            if (i&(i-1))==0: k+=1
            x=((x<<k)|i)%mod;
        return x