Link 在 C 表达式中模运算和按位与之间

Question

我发现了一个使用按位逻辑执行漂亮的模块化算术运算的 C 代码片段：

int a,b,c; 
c = (a + b - 1) & (- b) +b;

c 的值是 b 大于 a+b 的最小倍数（根据 John Bollinger 的回答编辑）。我试图向自己解释这是如何工作的（我对模块化算术和 & 操作如何相关的理解很薄弱）但是我缺乏洞察力。另一方面它看起来像我可以表达为

c = (a+b) - ((a+b)%b) + (((a+b)%b)?b:0)

这个表达很容易理解。此外，模块化的外观和？操作表明各个部分可以表示为按位逻辑，并且 以某种方式 简化为顶部的表达式。但是怎么办？如果有人想试一试，我会把它留作练习（这不是家庭作业）。实现不需要在 C 中，如果有解释这一点的在线参考，欢迎您提供它，但不会是完整的答案。我希望看到从底部到顶部的表达式以清晰的步骤过渡...

评论 This link 表明当 b 是 2 的幂时这可能适用。 other link 解释了按位 & 不分布在加法上。

假设在表达式 ...&(-b) 中，(-b) 可以替换为 (nums(int)-b)，其中 nums(int) 是表示中可能的整数总数。

请随意指定您最喜欢的 compiler/C 版本。

示例代码：

int a,b,c;
int alow, ahigh; 

b = 16;
alow = 8; 
ahigh = 20; 
printf("a+b      c    lcm(a+b,b) + ?b  \n");    
for (a=alow;a<ahigh;a++) {
    c = ((a+b-1) & (-b)) +b;
    printf("%5d   %5d    %5d   \n",a+b, c, (a+b) - ((a+b)%b) + (((a+b)%b)?b:0) );
}

示例输出：

  a+b      c    lcm(a+b,b) + ?b
   24      32       32
   25      32       32
   26      32       32
   27      32       32
   28      32       32
   29      32       32
   30      32       32
   31      32       32
   32      32       32
   33      48       48
   34      48       48
   35      48       48

Answer 1

我不相信你从中得到的任何结果。根据 C Standard, section 6.5:

Some operators (the unary operator ~,and the binary operators <<, >>, &, ^, and |, collectively described as bitwise operators) are required to have operands that have integer type. These operators yield values that depend on the internal representations of integers, and have implementation-defined and undefined aspects for signed types.

Answer 2

在使用二进制补码表示负数的机器上，如果 b 是 2 的幂，那么在 -b 的表示中，最低有效的 log2(b) 位具有值零，所有其他位的值为一。解释为无符号值时，该位模式中的最低有效二进制数字具有位值 b。（示例：int8_t 和值 -4 在这样的表示中具有位模式 11111100。）这是当今使用的最常见的整数表示样式，在重要的地方，其余的这个答案的一部分将假设负整数表示的模式。

这样的值可以用作位掩码，以从非负整数中屏蔽掉位值小于 b 的二进制数字。鉴于我们假设二进制表示和 b 2 的幂，屏蔽掉具有较低位值的位必然导致值可被 b.

整除

现在假设a是非负的，b是2的幂。a的值可以表示为[=16=的非负倍数]加上余数：

a == n * b + a % b

现在考虑表达式 (a + b - 1)，并假设计算它的值不会导致整数溢出。有两种情况：

案例 1：`a % b == 0`

在这种情况下，a == n * b，所以

(a + b - 1) == n * b + b - 1

。如果我们屏蔽掉位值小于 b 的位，我们得到

(a + b - 1) & (-b) == n * b == a

这肯定是b大于等于a的最小倍数。

案例二：`a % b != 0`

在这种情况下，

(a + b - 1) == (n + 1) * b + a % b - 1

。如果我们屏蔽掉位值小于 b 的位，我们得到

(a + b - 1) & (-b) == (n + 1) * b

由于 a 严格介于 n * b 和 (n + 1) * b 之间，这又是 b 大于或等于 a 的最小倍数。

因此，您的原始断言

The value of [(a + b - 1) & (-b)] is the next largest number greater than a+b that is divisible by b

是我假设的数字表示的不准确表征（包括 b 不是 2 的幂，尽管我没有证明这一点）。相反，在上述假设下，表达式计算大于或等于 a.

的 b 的最小倍数

你修改后的断言直接来自上面的断言，但是，通过在表达式的两边添加 b。如果 (a + b - 1) & (-b) 是 b 的最小倍数，并且至少与 a 一样大，那么 (a + b - 1) & (-b) + b 是 b 的最小倍数，即至少和 a + b.

一样大

不依赖于数字表示（但仍然对溢出敏感）的等价表达式是

((a + b - 1) / b) * b + b

((a + b) / b) * b + b

((a / b) + 1) * b + ((a % b) ? b : 0)

这些映射中的最后一个直接映射到上面给出的两个案例，稍加注意就可以将其重新排列为您在问题中提出的第二个表达式。

Link 在 C 表达式中模运算和按位与之间

Link between modular arithmetic and bitwise AND in C expression

c

bitwise-and

modular-arithmetic

案例 1：`a % b == 0`

案例二：`a % b != 0`

Link 在 C 表达式中模运算和按位与之间

Link between modular arithmetic and bitwise AND in C expression

c

bitwise-and

modular-arithmetic

案例 1：a % b == 0

案例二：a % b != 0

案例 1：`a % b == 0`

案例二：`a % b != 0`