【Python】实现按位右移补零操作(同java中的>>>操作)

发布时间 2023-04-23 19:51:27作者: Alan_LJP

答案

# Python代码,模拟Java中int型的数的按位右移补零操作
def right_shift(val, n):
    return (val % 0x100000000) >> n

  
  

逐步推导和解释

推论一:对于一个32位的(int型的)二进制,Python中的>>操作 等同于 Java种的>>>操作

证明如下:
 Python中:binary_value>>n是该二进制整体右移n位,然后在左边补n个0
 Java中:binaryValue>>>n是该二进制整体右移n位,然后在左边补n个0
 故,Python中的binary_value>>n 等同于 Java中的binaryValue>>>n

结论:
 如果一个数在Python和Java中的二进制形式是一致的,则Python中的binary_value>>n 等同于 Java中的binaryValue>>>n

推论二 :对于相等的python_value(十进制)和javaValue(十进制),若为负数则二进制不一致,若为正数则二进制一致

举例如下:
 假设一:python_value=-45(十进制),javaValue=-45(十进制)
 那么,python_value转二进制的值为-0b101101,而javaValue转二进制的值为:0b1111_1111_1111_1111_1111_1111_1101_0011
 所以,当前这两个二进制是不相等的

 假设二:python_value=45(十进制),javaValue=45(十进制)
 那么,python_value转二进制的值为0b10_1101,而javaValue转二进制的值为:0b0000_0000_0000_0000_0000_0000_0010_1101
 所以,当前这两个二进制是相等的
 注:二进制的最左边塞0不影响这个值,比如:0b10_1101 = 0b0010_1101(在十进制中也是一样的,比如233=0233=000233)

证明如下:
 Python中的负数的二进制是:找到负数的绝对值的二进制,然后在最左边加上负号
  比如-45,找到45的二进制0b10_1101
  然后在最左边加负号得到-0b10_1101
 而Java中的负数的二进制是:找到负数的绝对值的二进制,然后每个位数取反,然后再加1
  比如-45,找到45的32位二进制0b0000_0000_0000_0000_0000_0000_0010_1101
  然后取反得到:0b1111_1111_1111_1111_1111_1111_1101_0010
  最后加1得到:0b1111_1111_1111_1111_1111_1111_1101_0011
 因为Python和Java对于给出负数的二进制的机制不一样
 所以,该负数在两种语言下表现出的二进制不同

 Python中的正数的二进制是:找到正数的二进制
 Java中的正数的二进制是:找到正数的二进制
 所以,该正数在两种语言下表现出的二进制相同

结论:
 如果数为负数,则十进制相等的python_value和javaValue的二进制不一致
 如果数为非负数(零/正数),则十进制相等的python_value和javaValue的二进制一致

推理三:32位的int型的二进制+该二进制的反码 = 2^32-1(十进制)

证明过程:

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□        32个格子
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn        其中n为0或1
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu        其中u为1或0,是对应位数的n的取反的值
某一位上(竖着看)的n+u必然为1,因为它两是“相反的”,即一个为1,则另一个必然为0
所以
   nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
+  uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
───────────────────────────────────
= 111111111111111111111111111111111(二进制) = 2^32-1(十进制)

推论四:若python_value=javaValue=负数,则在Python语言下:-python_value(正)在Python下的二进制 + javaValue(负)在Java下的二进制 = 2^32(十进制)

推理的解释说明如下:
 若 python_value 和 javaValue 的十进制的值相等,且都为负数,比如它两都是-45
 将 -python_value 转成Python语言下的二进制(比如 0b101101),将 javaValue 转成Java语言下的二进制(比如 0b1111_1111_1111_1111_1111_1111_1101_0011)
 然后,在Python语言下将转化后的两个数相加,即:0b101101 + 0b1111_1111_1111_1111_1111_1111_1101_0011
 那么,最终值为0b100000000000000000000000000000000(二进制),即2^32(十进制)或4294967296(十进制)或0x100000000(十六进制)
 注:Python中不存在两数相加后数据溢出,所以最终值就是2^32(十进制)

常识一说明:
 二进制转十进制的操作是(第xx位的数字是从右边开始数):

 a) 当符号位为0(正数)时候: +第32位的数字(为0)×2^31 + 第31位的数字×2^30 + 第30位的数字×2^29 + ...... + 第2位的数字×2^1 + 第1位的数字×2^0
    例如计算二进制是 0000_0000_0000_0000_0000_0000_0000_1101 的十进制的值,套计算公式则为:
        0         0        0        0....0   0       1       1       0       1
       +0×2^31 + (0×2^30 + 0×2^29 + ...... + 0×2^4 + 1×2^3 + 1×2^2 + 0×2^1 + 1×2^0)
       = 2^3 + 2^2 + 2^0       (去掉为0的数)
       = 8 + 4 + 1
       = 13
b) 当符号位为1(负数)时候:-第32位的数字(为1)×2^31 + 第31位的数字×2^30 + 第30位的数字×2^29 + ...... + 第2位的数字×2^1 + 第1位的数字×2^0
   例如计算二进制是 1111_1111_1111_1111_1111_1111_1111_0011 的十进制的值,套计算公式则为:
       1         1        1        1....1   1       0       0       1       1
       -1×2^31 + (1×2^30 + 1×2^29 + ...... + 1×2^4 + 0×2^3 + 0×2^2 + 1×2^1 + 1×2^0)
       = -2^31 + 2^30 + 2^29 + ... + 2^4 + 2^1 + 2^0       (去掉为0的数)
       = -13       (计算过程忽略)
       其实,-2^(n+1) + 2^n = -2^n,所以上面的可以直接简化为:
       = [(-2^31 + 2^30) + 2^29 + ... + 2^4] + 2^1 + 2^0
       = [(-2^30 + 2^29) + ... + 2^4] + 2^1 + 2^0
       = ...
       = [(-2^5 + 2^4)] + 2^1 + 2^0
       = -2^4 + 2^1 + 2^0
       = -16 + 2 + 1
       = -13

证明如下:
 对于一个-python_value(正数十进制),在Python中假设它的二进制为:0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA(共32位,最高位是0,其中A为0或1)
 ∵ python_value = javaValue = 负数,而将javaValue(负数十进制)转化为二进制的步骤为:先找到它的正数的二进制,再将每个位数取反,然后再加1
 ∴ javaIntValue(负数十进制) = -javaIntValue(正数十进制)取反 + 1 = -python_value(正数十进制)取反 + 1
  现假设:javaIntValue(负数十进制) = 0b1CCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC(二进制)
 ∴ 0b1CCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC = [(0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA)取反] + 1
  = (2^32 - 1 - 0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA) + 1   # 推论三
  = 2^32 - 0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA
 ∴ 0b1CCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC = 2^32 - 0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA   # 等式一

 现在在Python语言下且python_value=javaValue=负数的情况下计算:-python_value(正数十进制)在Python下的二进制 + javaValue(负数十进制)在Java下的二进制
 即在Python语言下计算:0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA + 0b1CCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC
 = 0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA + (2^32 - 0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA)   # 利用等式一
 = 2^32

结论:
 在Python语言下:0b0AAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA_AAAA + 0b1CCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC_CCCC = 2^32

推论五:若python_value=javaValue=正数,则:python_binary(python_value) = javaBinary(javaValue)

注:这里的正数严格来说是:非负数(零/正数),这样写只是为了更好的区分推理三和推理四
证明如下:
 对于一个python_value(正数十进制),将其转化为二进制的步骤为:找到它的二进制
 对于一个javaValue(正数十进制),将其转化为二进制的步骤为:找到它的二进制

结论:
 若python_value=javaValue=非负数,则它两的二进制相同


  

推论总结:

  1. 若 python_value(int型)>=0,则 python_value>>n 即可模拟Java中int型的数的按位右移补零操作
    证明:利用推论一和推论五
  2. 若 python_value(int型)<0,则将python_value转成Java语言下的二进制形式,然后>>n即可,即 (2**32+python_value)>>n 即可模拟Java中int型的数的按位右移补零操作
    证明:利用推论一和推论四

注一:
一个数,其表现形式可以为二进制/十进制/十六进制,但是其本质就是一个数而已
也就是说,对于这个数,对其的二进制做操作,等同于对其的十进制/十六进制做操作,因为本质是对这个数做操作
 比如:因为0b101101(二进制) = 45(十进制) = 0x2d(十六进制),所以:0b101101>>3 = 45>>3 = 0x2d>>3 = 3
所以,对python_value这个int型的数做右移n位的操作,等同于对其二进制形式做右移n位的操作;反过来说也一样

注二:
一个Java中的负数的二进制:0b1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx,在Python看来是个正数,因为我们可以认为Python中的二进制是无限位的
也就是说,在Python看来 这个0b1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx的最高位其实是0而不是1
也就是说,在Python看来这个数其实是:0b01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 或 0b000001xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx (前面很多0)
 比如:-45在Java中的二进制是0b1111_1111_1111_1111_1111_1111_1101_0011,在Python中这个二进制转十进制的值是:4294967251
 根据推论四, |-45| + 4294967251 = 2**32 = 4294967296


  

Python实现

Python代码

def unsigned_right_shift(value: int, n: int) -> int:
    if value >= 0:  # value为非负数,直接使用>> (推论总结中的1)
        return value >> n
    else:           # value为负数,将其转化为在Java语言下的二进制,然后使用>> (推论总结中的2)
        return (2**32 + value) >> n

但是,上述代码有个缺点:默认value是个int型的值,也就是默认value的取值范围是:[-2^31, 2^31-1],如果超出这个范围,结果将会错误,即和Java的>>>结果不一致
因为标题是:模拟Java中int型的数的按位右移补零操作,是int型的数
所以还需要考虑value不在[-2^31, 2^31-1]范围内的情况

常识二说明:
 Java中long转int,将后32位的二进制保留,即从long的右边数32位保留作为int的值,其余的左边/前面的值舍弃
 那么在上述的Python代码中的最前面加代码:保留这个数的二进制的后32位(或者叫将其转为int型)
即:
 value & 0b11111111111111111111111111111111
 value & (2**32)
 value & 0xffffffff
故Python代码为:

def unsigned_right_shift(value: int, n: int) -> int:
    value = value & 0xffffffff
    if value >= 0:  # value为非负数,直接使用>> (推论总结中的1)
        return value >> n
    else:           # value为负数,将其转化为在Java语言下的二进制,然后使用>> (推论总结中的2)
        return (value + 0x100000000) >> n

Python代码优化

常识三说明(在Python中):
 1. 若a和b都是正整数,且0<a<b,那么:a//b=0
 2. 若a和b都是整数,且a<0<b,那么:a//b=-1
 3. a对b取模,即a%b=a-(a//b)*b

且还有此推论A:若value>=0,则 value % 0x100000000 == value
证明如下:

  value % 0x100000000
= value - (value // 0x100000000) * 0x100000000    常识三第3条
= value - (0) * 0x100000000    常识三第1条
= value    得证

所以,有此推论B:若value<0,则 value % 0x100000000 == value + 0x100000000   (%是求模符号,不是取余)
证明如下:

  value % 0x100000000
= value - (value // 0x100000000) * 0x100000000    常识三第3条
= value - (-1) * 0x100000000    常识三第2条
= value + 0x100000000    得证

所以,Python代码中的if-else代码可以写为:

def unsigned_right_shift(value: int, n: int) -> int:
    value = value & 0xffffffff
    if value >= 0:
        return (value % 0x100000000) >> n   # 推论A:value == value % 0x100000000
    else:
        return (value % 0x100000000) >> n   # 推论B:value + 0x100000000 == value % 0x100000000

因为无论if-else的条件是什么,最后都是返回(value % 0x100000000) >> n,所以可以写成:

def unsigned_right_shift(value: int, n: int) -> int:
    value = value & 0xffffffff
    return (value % 0x100000000) >> n

  

那么,最终的代码就是:

def unsigned_right_shift(value: int, n: int) -> int:
    return ((value & 0xffffffff) % 0x100000000) >> n    # 加括号是为了避免过分依赖优先级!

到此,你可能发现最终代码和一开始给的答案不一致,多了一个 (value & 0xffffffff) 强转为int型的数
答案这么写是因为,是要在Python中模拟:在Java中对一个int类型的数使用>>>操作;
注意,在Java中这个操作的前提条件就是这个数是int类型的(否则报错/报告警),所以其实value的值的范围是int类型的范围,所以无需考虑value超出范围的情况

因此,答案可以简写为:

def right_shift(value, n):
    return (value % 0x100000000) >> n

  
  

参考

How to get the logical right binary shift in python