-1

我遇到了一个 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 中，如果有一个在线参考解释了这一点，欢迎您提供它，但不会是一个完整的答案。我想以清晰的步骤看到从底部到顶部表达式的过渡......

评论 此链接表明当 b 是 2 的幂时这可能适用。此其他链接解释了按位 & 不分布在加法上。

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

随意指定您最喜欢的编译器/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
4

2 回答 2

4

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

诸如此类的值可以用作位掩码，以屏蔽位值小于b非负整数的二进制数字。假设我们假设二进制表示和b2 的幂，屏蔽具有较低位值的位必然会导致值可被 整除b。

现在假设a是非负的并且b是 2 的幂。 的值a可以表示为非负倍数b加上余数：

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的最小倍数。ba

因此，您最初的断言是

[(a + b - 1) & (-b)] 的值是大于 a+b 且能被 b 整除的下一个最大数

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

但是，您修改后的断言直接来自上面，通过添加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)

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

于 2015-04-13T17:51:15.357 回答
1

我不会相信你从中得到的任何结果。根据C 标准，第 6.5 节：

某些运算符（一元运算符 ~ 和二元运算符 <<、>>、&、^ 和 |，统称为按位运算符）需要具有整数类型的操作数。这些运算符产生的值取决于整数的内部表示，并且具有符号类型的实现定义和未定义方面。

于 2015-04-13T17:25:36.450 回答