两个bitset类型的数据进行模2^n加法

模$2^n$加法即两个n位的二进制数相加，结果大于$2^n$，则丢掉溢出的进位，剩余的结果即为所求

思路

两位2进制数相加，使用如下公式：
$sum = aoplus b oplus carrier$
$carrier = a&b$
只要循环计算两次，就不再有进位，即carrier结果即为0

证明

令 ： $X=x_{n}x_{n-1}x_{n-2}...x_1$
$Y = y_{n}y_{n-1}y_{n-2}...y_1$
$carrier = c_{n}c_{n-1}c_{n-2}...c_1= X & Y$
$sum = aoplus b oplus carrier$ 对第 i bit进行分析， $c_i=x_i&y_i$ ,若要ci 有两次进位，需要 $sub_X=x_ix_{i-1}...x_1 = 2^{i-1}$ , $sub_Y=y_iy_{i-1}...y_1 = 2^{i -1}$ 但 $sub_X <= 2^{i-1} - 1 , sub_Y <= 2^{i-1} - 1$,因此不可能有两次进位 程序如下,为mod 23运算，可自行更改bitset的位数： #include #include using namespace std; bitset<3>& ModeTwoAdd(bitset<3>& a, bitset<3>& b) { bitset<3> c, c2, s; //the first carrier c = a & b; s = a ^ b; // the hightest carrier is neglected c2 = c << 1; c = s & c2; s = s ^ c2; // the hightest carrier is neglected c2 = c << 1; s = s ^ c2; return s; } int main(int argc, char const *argv[]) { bitset<3> a; bitset<3> b; bitset<3> sum; a = 5; b = 6; // sum = a + b = 11 mod 8 = 3; cout <<"a = "<< a << ", b = " << b << endl; sum = ModeTwoAdd(a,b); cout <<"sum = " << sum << endl; } 结果：5+6 = 11 ，11 mod 8 = 3；