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

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