常用知识点：
n&(n-1)的性质：把 n 的二进制位中最低位的 1变为0&运算，通常用于将某一位置为 0^的特性：无进位加法
剑指 Offer 64. 求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
class Solution:
def sumNums(self, n: int) -> int:
return n and n+self.sumNums(n-1)
# and 的特性：
# a and b 返回 b, a and 0 返回 a
172. 阶乘后的零
给定一个整数 n，返回 n! 结果尾数中零的数量。
class Solution:
def trailingZeroes(self, n: int) -> int:
cnt = 0
while n >= 5:
n //= 5
cnt += n
return cnt
# 数学观察
60. 排列序列
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
“123”，”132”，”213”，”231”，”312”，”321”
给定 n 和 k，返回第 k 个排列。
class Solution:
def getPermutation(self, n: int, k: int) -> str:
ans=""
factroial=[1]
for i in range(1,n):
factroial.append(i*factroial[-1])
valid=[1]*(n+1)
k-=1
for i in range(1,n+1):
order=k//factroial[n-i]+1
for j in range(1,n+1):
order-=valid[j]
if order==0:
ans+=str(j)
valid[j]=0
break
k %= factroial[n-i]
return ans
#康托展开，不懂
204. 计数质数
class Solution:
def countPrimes(self, n: int) -> int:
if n<3: return 0
ans=[1]*n
for i in range(2,int(n**0.5)+1):
ans[2*i::i]=[0]*len(ans[2*i::i]) #这样赋值比一个个遍历赋值快好多
return sum(ans)-2
#埃氏筛
#那个i的范围还是没懂
231.2的幂
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n>0 and n&(n-1)==0
说明：
| num | n | n-1 | n&(n-1) |
|---|---|---|---|
| 2**0 | 0001 | 0000 | 0000 |
| 2**1 | 0010 | 0001 | 0000 |
| 2**2 | 0100 | 0011 | 0000 |
191. 位1的个数
返回一个无符号整数（以二进制串的形式）中数字位数为 ‘1’ 的个数。
class Solution:
def hammingWeight(self, n: int) -> int:
ans = 0
while n:
ans += 1
n &= (n-1)
return ans
记住：n&(n-1) 的性质：把 n 的二进制位中最低位的 1变为0
136.只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(lambda x, y: x ^ y, nums)
#reduce(function, iterable[, initializer])内置函数
#异或运算的特性：a^a=0，a^0=a
268. 丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
res = reduce(lambda x,y:x^y,range(n+1))
for num in nums:
res ^= num
return res
利用异或的特性
190. 颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
1. 循环
class Solution:
def reverseBits(self, n: int) -> int:
ans = 0
for i in range(32):
ans <<= 1
ans += (n & 1)
n >>= 1
return ans
483. 最小好进制
对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。
枚举k进制后的数位长度
class Solution:
def smallestGoodBase(self, n: str) -> str:
n = int(n)
for m in range(n.bit_length(), 2, -1):
k = int(n**(1/floor(m-1)))
if (k**m-1)//(k-1) == n:
return str(k)
return str(n-1)
371. 两整数之和
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
提示：
1. 无进位加法使用 异或 计算得出
2. 进位结果使用 与运算和移位 计算得出
3. -1000 <= a, b <= 1000
class Solution:
def getSum(self, a: int, b: int) -> int:
while b != 0:
carry = ((a&b)<<1)%2**32
a = (a^b)%2**32
b = carry
if a&2**31:
return ~((a^2**31)^(2**31-1))
else:
return a
# 由于python的int不是32位, 所以我们需要模拟32位, 方法就是把高于32位全部忽略, 我们通过0xFFFFFFFF作为mask, 相与来实现
# 再返回结果的时候, 由于后32位之前全是0, 负数可能会被识别为正数, 所以如果答案是负数, 需要把前面的0变成1, 后32位不变.
class Solution:
def getSum(self, a: int, b: int) -> int:
mask = 0xFFFFFFFF
a = a & mask
b = b & mask
while (b != 0):
carry = (a & b) << 1
carry = carry & mask
a = a ^ b
b = carry
a = a & mask
# a高于后32位全是0
if a < 0x80000000: # 后32位的最高位是0, 说明实际结果不是负数, 直接返回
return a
else: # 后32位的最高位是1, 说明实际结果是负数, 如果直接返回, 由于a高于32位全是0, 解释器会把a解释成一个大的正数, 所以必须把高位的0变成1,而低位不变解释器才能得到正确的答案
return ~(a^mask)
