LeetCode1680：连接连续二进制数字

十进制数字在位运算下就已经是二进制，使用位运算可以方便的拼接。关键是怎么保证不溢出。分析下计算流程，假设当前的运算结果是\(A\)，下一位数字的位长是 \(w\) ，值是 \(i\) 。那么我们的运算实际上就是 \(A_{new}=A*2^w+i\) 。如果熟悉模运算可以看出 \(A_{new}(mod m)=A(mod m)*2^w(mod m)+i(mod m)==((A(mod m))*2^w+i)(mod m)\) 。即先对上一次的结果取模再运算。与运算完再取模的结果是相同的，可以直接在循环中取模。

class Solution:def concatenatedBinary(self, n: int) -> int:MOD=1_000_000_007ans=0for i in range(1,n+1):w=i.bit_length()# 通过位运算拼接二进制串，利用同余的性质在循环中取模ans=(ans<<w|i)%MODreturn ans