位运算，移动进位位

Question

目标是能够做到：

struct.pack('!H', x)

但如果 x 大于 65535，那么这将因显而易见的原因而失败。
我不是一个精通位操作的巫师，但我理解 << 操作将失去任何移动的位。但我不知道如何从二进制/字节字符串中提取一个或多个进位位，并将进位值添加到尾随进位字节的两个字节集中。

我需要每次遍历2个字节的字节串并将它们与前两个字节相加。偶尔会生成大于 65535 的值, 这就是我需要从结果中提取进位位的地方，并对结果进行 + 运算，以及进位位本身（见下图）。

这是我想要完成的事情: （在这种情况下，只有一个进位位，而2个尾随字节将得到 +1 作为结果。）

这是我目前获得的内容：

from struct import unpack, pack
from binascii import *

even_bytes_string = b'\x45\x00\x00\x3c\x1c\x46\x40\x00\x40\x06\xac\x10\x0a\x63\x‌​ac\x10\x0a\x0c'
result = None
for i in range(0, len(even_bytes_string)-1,2):
    if not result:
        result = unpack('!H', even_bytes_string[i:i+2])[0]
        continue

    result += unpack('!H', even_bytes_string[i:i+2])[0]
    if result > 65535:
        # Got a carry bit.
        pass

    print(result)
    print(pack('!H', result))

我真的不知道如何完成这个相当简单的任务，而不将加法操作的结果转换为实际的二进制表示形式（11001...）然后进行字符串处理s = s[-16:]+s[:-16]（过于简化），最后将其转回一组2字节。这似乎不太实用、快速或正确。

我希望你们中的一个熟练掌握Python位操作的人告诉我如何正确地完成此操作。肯定有方法的。

我尝试完成的稍微更混乱的图像（保持结果为2字节，在其中删除任何进位位并将它们作为“单独”的值添加到结果中）。：

- Torxed

---

@Tryph 我刚意识到我只需要将进位位（可能有多个）添加到两组字节中。所以我的问题需要更新。 - Torxed

与，移位，或。 - Ignacio Vazquez-Abrams

你的代码中有些地方让我想起了UTF-8编码算法。 - GIZ

@TorkelBjørnson-Langen 我是否误解了这篇 Stack Overflow 帖子：https://dev59.com/Q3VC5IYBdhLWcg3w7V73 请注意，这些不是循环移位。被移位的数字“从末尾掉落”的部分将会丢失，而不是绕回到开头。 - Torxed

@Torxed 首先在Python中添加这两个数字（整数精度将根据需要进行扩展）。然后，在您引用的页面上，看起来示例所做的不仅仅是 (x & 0xFF) + (x >> 16)。 - jez

Answer 1

这个过程只是(x & 0xFFFF) + (x >> 16)。不需要使用<<运算符。这里是你引用的实例的实现代码：

def addwrap16( a, b ):
    c = a + b
    w = ( c & 0xFFFF ) + ( c >> 16 )
    print(' {:04x} ->  {:016b}'.format(a, a))
    print(' {:04x} ->  {:016b}'.format(b, b))
    print('{:05x} -> {:017b}'.format(c, c))
    print(' {:04x} ->  {:016b}'.format(w, w))
    print('')
    return w

import struct, functools
even_bytes_string = b'\x45\x00\x00\x3c\x1c\x46\x40\x00\x40\x06\xac\x10\x0a\x63\xac\x10\x0a\x0c'
vals = struct.unpack( '!' + 'H' * ( len( even_bytes_string ) // 2 ), even_bytes_string )
result = functools.reduce(addwrap16, vals)

它会输出以下内容：

 4500 ->  0100010100000000
 003c ->  0000000000111100
0453c -> 00100010100111100
 453c ->  0100010100111100

 453c ->  0100010100111100
 1c46 ->  0001110001000110
06182 -> 00110000110000010
 6182 ->  0110000110000010

 6182 ->  0110000110000010
 4000 ->  0100000000000000
0a182 -> 01010000110000010
 a182 ->  1010000110000010

 a182 ->  1010000110000010
 4006 ->  0100000000000110
0e188 -> 01110000110001000
 e188 ->  1110000110001000

 e188 ->  1110000110001000
 ac10 ->  1010110000010000
18d98 -> 11000110110011000
 8d99 ->  1000110110011001

 8d99 ->  1000110110011001
 0a63 ->  0000101001100011
097fc -> 01001011111111100
 97fc ->  1001011111111100

 97fc ->  1001011111111100
 ac10 ->  1010110000010000
1440c -> 10100010000001100
 440d ->  0100010000001101

 440d ->  0100010000001101
 0a0c ->  0000101000001100
04e19 -> 00100111000011001
 4e19 ->  0100111000011001

- jez

---

“<<”只是我希望能派上用场的位移示例，但很快发现它没有用。 “>>”或“|”操作也不行。这似乎就是解决方法！ :) - Torxed

手动计算我预期的值，使用我的解决方案和你的解决方案 - 它们都得出了相同的结论。在查看tcpdump时，它似乎是一个有效的网络校验和头，所以我对这个更高效的解决方案非常满意！非常感谢你的答案，我甚至理解了为什么这个方法可行的逻辑 :) - Torxed

Answer 2

好的，这不是最优雅的解决方案，也不确定是否准确，但至少不会破坏struct.pack()函数。

基于@Tryph提出的一个简单问题，我想到了以下解决方法：

from struct import unpack, pack
from binascii import *

even_bytes_string = b'\x45\x00\x00\x3c\x1c\x46\x40\x00\x40\x06\xac\x10\x0a\x63\x‌​ac\x10\x0a\x0c'
result = None
for i in range(0, len(even_bytes_string)-1,2):
    if not result:
        result = unpack('!H', even_bytes_string[i:i+2])[0]
        continue

    result += unpack('!H', even_bytes_string[i:i+2])[0]
    if result > 65535:
        tmp = pack('!I', result)
        carry = unpack('!H', tmp[:2])[0]
        result = unpack('!H', tmp[2:])[0]+carry

    print(result)
    print(pack('!H', result))

将较大的数字视为Int而不是Short，这使我可以将两个前置字节视为进位，并将它们添加到尾随的两个字节之上。这不太优雅，但可能有效？

- Torxed