位运算(Bitwise Algorithms)
1 位运算基础知识
1. 与：&，有0取0，全为1时结果为1
2. 或：|，有1取1，全为0时结果为0
3. 非：~，对每位二进制取反
4. 异或：^，二进制位相同为0，不同为1
5. 左移：<<，左移n位相当于乘以2的n次方
6. 右移：>>，右移n位相当于除以2的n次方
2 异或技巧
A⨁B⨁B=A => A⨁0=A
自己和自己异或是0，同时，自己和0异或就是自己。总结下来就是：如果存在偶数个自身相异或，那么最终结果是0；如果存在奇数个自身相异或，那么最终结果是自身。
2.1 在连续的自然数当中，有一个数重复了，如何设计算法将它找到，不用辅助空间。
A⨁A⨁B⨁B⨁C⨁C⨁C⨁... => C⨁0=C
def find_repeat_number_bitwise(numbers, start):
"""异或位运算，时间：O(n), 空间：O(1)
:param numbers: List
:return: ret
"""
result = '输入参数错误，请传入元素至少为2的List'
if isinstance(numbers, list) and len(numbers) >= 2:
result = numbers[-1]
for i in range(len(numbers) - 1):
result ^= numbers[i] ^ (start + i)
return result
def find_repeat_number(numbers):
"""排序遍历，时间：O(nlog2n), 空间：O(1)
:param numbers: List
:return: ret
"""
result = '输入参数错误，请传入元素至少为2的List'
if isinstance(numbers, list) and len(numbers) >= 2:
numbers.sort()
for i in range(1, len(numbers)):
if numbers[i] == numbers[i - 1]:
result = numbers[i]
break
return result
2.2 输入两个数，从一个数变到另一个数需要改变几位二进制才可以实现。
def difference_between_numbers(num1, num2):
"""计算两个数二进制位不同的位数
:param num1: number 1
:param num2: number 2
:return: 两个数二进制位不同的位数
"""
if isinstance(num1, int) and isinstance(num2, int):
return bin(num1 ^ num2)[2:].count('1')
else:
return '输入数据类型错误，请输入整数'
3 与运算技巧
3.1 如何判断一个数是否为2的整数次幂，如：1024是，127不是。
def is_integer_power_of_two(num):
"""判断一个数是否为2的整数次幂
:param num: number
:return: True/False
"""
if isinstance(num, int):
return num & (num - 1) == 0
else:
return '输入数据类型错误，请输入整数'
4 与运算和异或技巧
4.1 现在给定一个数，我们希望将这个数的奇偶位互换，如何设计算法将其实现。
def swap_odd_even_pos(num):
"""互换一个整数的二进制奇偶位
:param num: number
:return: number
"""
if isinstance(num, int):
right = (num & int("0xaaaaaaaa", 16)) >> 1
left = (num & int("0x55555555", 16)) << 1
return right ^ left
else:
return '输入数据类型错误，请输入整数'
5 K进制转换和无进位加法技巧
5.1 现在有一组数，里面的数除了一个落单的数之外，其它数均只出现了k次，请问如何将这个落单的数找出来。
# 十进制无进位加法：A∗10+B∗10+C∗10+...+N+(N+1)∗10 = 0+0+0+...+N+0...= N
# K进制无进位加法：A∗K+B∗K+C∗K+...+N+(N+1)∗K = 0+0+0+...+N+0...= N
# 将所给列表中的数转换成K进制，然后做无进位加法
def base_conversion(num, base):
bit_string = "0123456789abcdefghijklmnopqrstuvwxyz"
return ((num == 0) and "0") or (base_conversion(num // base, base).lstrip("0") + bit_string[num % base])
def find_single_number(numbers, repeat):
"""找出列表中唯一未重复的落单数字
:param numbers: List
:param repeat: int, 重复次数
:return: number
"""
result = ['0']
for number in numbers:
repeat_system = base_conversion(number, repeat)
repeat_list = list(repeat_system)
repeat_list.reverse()
if len(result) < len(repeat_list):
result, repeat_list = repeat_list, result
for i in range(len(repeat_list)):
result[i] = int(result[i], repeat) + int(repeat_list[i], repeat)
if result[i] >= repeat:
result[i] -= repeat
result[i] = base_conversion(result[i], repeat)[-1]
result.reverse()
return int(''.join(result), repeat)
6 变换迁移
6.1 找出两个落单的数，其它数出现了两次，只有两个落单的数在列表中只出现了一次，我们如何将其找出？
A⨁A⨁B⨁B⨁...⨁N⨁(N+1)⨁... = N⨁(N+1)
分组 + 异或
6.2 奇怪的捐赠，地产大亨Q先生临终的遗愿是：拿出100万元给X社区的居民抽奖，以稍慰藉心中愧疚。麻烦的是，他有些很奇怪的要求：
- 100万元必须被正好分成若干份（不能剩余）。每份必须是7的若干次方元。比如：1元, 7元，49元，343元，…
- 相同金额的份数不能超过5份。
- 在满足上述要求的情况下，分成的份数越多越好！
# 进制数也可以用来解关于数的组合，化成7的次方组合
# 参考：总共分为16份，1*1, 7*1, 49*3, 343*3, 2401*3, 16807*3, 117649*1, 823543*1
def base_conversion(num, base):
bit_string = "0123456789abcdefghijklmnopqrstuvwxyz"
return ((num == 0) and "0") or (base_conversion(num // base, base).lstrip("0") + bit_string[num % base])
def distribution_of_donation(donation):
"""按7的整数次方分配总捐赠
:param donation: 总金额
:return: 总份数
"""
seven_system = base_conversion(donation, 7)
result = 0
for bit in seven_system:
result += int(bit)
return result
7 其它常见用法
7.1 与(&)代替取余(%)判断奇偶数
def judge_odd_number_with_remainder(num):
"""取余数判断奇偶数
:param num: number
:return: True/False
"""
return num % 2 == 1
def judge_odd_number_with_and(num):
"""位运算与判断奇偶数
:param num: number
:return: True/False
"""
return num & 1 == 1
7.2 左移代替乘法，右移代替除法
# 只适用于2的n次方的整乘/除
def multiplication_by_power_two(num, power):
return num << power
def division_by_power_two(num, power):
return num >> power