datetime:2024/03/01 14:15
author:nzb
位运算
题目一
给定两个有符号32位整数a和b，返回a和b中较大的。
- 【要求】不用做任何比较判断。
def flip(n):
"""
:param n: 0 or 1
:return:
"""
return n ^ 1
def sign(n):
"""
取符号位
负数-> 1
正数-> 0
:param n:
:return:
"""
# n >> 31 取符号位
return flip(n >> 31 & 1)
def get_max1(a, b):
c = a - b # 可能会溢出
sc_a = sign(c) # a - b 为负， sc_a 为0， 否则为1
sc_b = flip(sc_a) # 取反，如果sc_a == 0, sc_b==1, 否则sc_a==1, sc_b==0
# sc_a==0, scb必为1，sc_a==1，sc_b必为0
# 把 if else做成了互斥条件相加的条件
return a * sc_a + b * sc_b
def get_max2(a, b):
c = a - b
sa = sign(a)
sb = sign(b)
sc = sign(c)
diff_s_ab = sa ^ sb # a和b符号一样为0，不一样为1
same_s_ab = flip(diff_s_ab) # 跟diff_s_ab互斥，符号一样为1，不一样为0
# 什么时候a比较大
# 1、a和b符号相同，a - b不会溢出，a - b > 0
# 2、a和b符号不同，并且 a > 0
return_a = diff_s_ab * sa + same_s_ab * sc # 加号两边互斥，有一个中都返回a
return_b = flip(return_a)
return a * return_a + b * return_b
print(get_max1(1, 2))
print(get_max1(-4, 8))
print(get_max2(1, 2))
print(get_max2(-4, 8))
题目二
判断一个32位正数是不是2的幂、4的幂
- 2的幂的特点，
2,4,6,8...，就是二进制数中某一位为1，只有唯一的1- 方法1：x取最右的1后等于0
- 方法2：x & x - 1 == 0
- 4的幂前提是2的幂
- 条件1：2的幂
- 条件2：偶数为1，比如
1(2^0), 4(2^2), 16(2^4), 64(2^6)->01, 100, 10000, 1000000, 偶数位为1, 并且唯一个1
def is_2_power(n):
"""只有唯一一个1"""
# 取出最右的1，与一下看还是不是原来的数
return n & (~n + 1) == n
# n - 1打乱，比如 00100 减一后是 00011
# return n & (n - 1) == 0
print(is_2_power(16))
print(is_2_power(3))
def is_4_power(n):
"""只有唯一一个1, 2的幂保证了，后面的看在不在偶数位上"""
# 0x5是0b101
return n & (n - 1) == 0 and n & 0x55555555 != 0
print(is_4_power(64))
print(is_4_power(63))
题目三
给定两个有符号32位整数a和b，不能使用算术运算符，分别实现a和b的加、减、乘、除运算
- 【要求】如果给定a、b执行加减乘除的运算结果就会导致数据的溢出，那么你实现的函数不必对此负责，除此之外请保证计算过程不发生溢出
加法
15 -> 01111
11 -> 01011
-------------
^ -> 00100 # 无进位新加
&<<1 -> 10110 # &<<1 进位信息
-------------
^ -> 10010
&<<1 -> 01000
-------------
^ -> 11010
&<<1 -> 00000 # 当没有进位信息的时候就是结果
# 需要保证用户给的a加b的结果不会溢出
def add(a, b):
while b != 0:
tmp = a & b
a = a ^ b
b = tmp << 1
return a
print(add(15, 11))
print(add(-9, -3))
print(add(-6, 7)) # 不行
print(add(6, -7)) # 不行
减法
def neg_num(n):
"""相反数"""
return add(~n, 1)
def minus(a, b):
return add(a, neg_num(b))
# print(minus(3, 2))
乘法
运算
27
34
----
108
81
----
918
二进制类似
011010 a
010110 b
--------
000000 ==0, a << 1, b >> 1
011010 !=0, add(res, a), a<<1, b>>1
011010 !=0, add(res, a), a<<1, b>>1
000000 ==0, a << 1, b >> 1
011010 !=0, add(res, a), a<<1, b>>1
-----------
0111111100 累加
def multi(a, b):
res = 0
while b != 0:
if b & 1 != 0:
res = add(res, a)
a <<= 1
b >>= 1
return res
print(multi(3, 5))
print(multi(-3, 5))
print(multi(-3, -5)) # 计算不出来
print(multi(3, -5)) # 计算不出来
除法
a 0110111
b 0000011
a 能不能减去 b << 31 ? 左移后比a大，所以不能，跳过
...
a 能不能减去 b << 15 ? 左移后比a大，所以不能，跳过
...
a 能不能减去 b << 4 ? b << 4 == 0110000能，a = a - b << 4 == 0000111
a 0000111
b 0000011
a 能不能减去 b << 3 ? b << 3 == 11000，不能，跳过
a 能不能减去 b << 2 ? b << 2 == 1100，不能，跳过
a 能不能减去 b << 1 ? b << 1 == 110，可以， a = a - b << 2 == 0000001
a 0000001
b 0000011
a 能不能减去 b << 0 ? b << 0 == 011，不能，跳过，a最后一个1是小余数，除不掉的
- 存在问题，TODO ```python def is_neg(n): return n < 0
def div(a, b): x = neg_num(a) if is_neg(a) else a y = neg_num(b) if is_neg(b) else b res = 0 for i in range(32)[::-1]: if (x >> i) >= y: # 为啥是x右移，因为y左移可能溢出 res |= (1 << i) x = minus(x, y << i) return neg_num(res) if is_neg(a) ^ is_neg(b) else res ```