我发现了很多关于按位除法的帖子,并且我完全了解大多数按位用法,但我想不出具体的除法。我想用所有可能的 2 的倍数来除一个给定的数字(比如说 100)(注意:我不想用 2 位倍数的幂来除!)
例如:100/2、100/4、100/ 6, 100/8, 100/10...100/100
我也知道,因为使用unsigned int
答案将被四舍五入,例如 100/52=0 但这并不重要,因为我可以跳过这些答案或打印出来,没问题。我最关心的是如何除以 6 或 10 等(2 的倍数)。需要用 C 来完成,因为我可以设法将你给我的任何代码从 Java 转换为 C。
3 回答
根据除以 3 问题的公认解决方案所示的数学运算,您可以推导出除法算法的递归式:
计算(int)
(X / Y)
- 令 k 满足 2 k ≥ Y 和 2 k-1 < Y
(注意,2 k =(1 << k)
) - 令 d = 2 k - Y
然后,如果 A =
(int)
(X / 2 k ) 且 B = X % 2 k,X = (1 << k) * A + B = (1 << k) * A - Y * A + Y * A + B = d * A + Y * A + B = Y * A + (d * A + B)
因此,
X/Y = A + (d * A + B)/Y
换句话说,
如果
S(X, Y) := X/Y
,那么S(X, Y) := A + S(d * A + B, Y)
。
这种重复可以用一个简单的循环来实现。循环的停止条件是分子低于 2 k时。该函数divu
实现递归,仅使用位运算符并使用无符号类型。数学运算的辅助函数未实现,但不应该太难(链接的答案add
已经提供了完整的实现)。该rs()
功能用于“右移”,它对unsigned
输入进行符号扩展。该函数div
是 的实际 API ,并在委托给 之前int
检查除以零和负数。做 2 的补码否定。y
divu
negate
static unsigned divu (unsigned x, unsigned y) {
unsigned k = 0;
unsigned pow2 = 0;
unsigned mask = 0;
unsigned diff = 0;
unsigned sum = 0;
while ((1 << k) < y) k = add(k, 1);
pow2 = (1 << k);
mask = sub(pow2, 1);
diff = sub(pow2, y);
while (x >= pow2) {
sum = add(sum, rs(x, k));
x = add(mul(diff, rs(x, k)), (x & mask));
}
if (x >= y) sum = add(sum, 1);
return sum;
}
int div (int x, int y) {
assert(y);
if (y > 0) return divu(x, y);
return negate(divu(x, negate(y)));
}
此实现取决于signed int
使用 2 的补码。为了获得最大的可移植性,div
应在调用divu
. 然后,它应该将divu
返回的结果从 2 的补码转换为原生签名表示。
以下代码适用于正数。当被除数或除数或两者都为负时,有标志来适当地改变答案的符号。
int divi(long long m, long long n)
{
if(m==0 || n==0 || m<n)
return 0;
long long a,b;
int f=0;
a=n;b=1;
while(a<=m)
{
b = b<<1;
a = a<<1;
f=1;
}
if(f)
{
b = b>>1;
a = a>>1;
}
b = b + divi(m-a,n);
return b;
}
/
尽可能多地使用运算符进行整数除法。
例如,当你想将 100 除以 6 或 10 时,你应该写100/6
or 100/10
。当您提到按位除法时,您是(1)表示运算符的实现/
还是(2)您指的是除以两个数字的幂。
对于 (1) 处理器应该有一个整数除法单元。如果不是,编译器应该提供一个好的实现。
对于 (2),您可以使用100>>2
而不是100/4
. 如果分子在编译时已知,那么好的编译器应该自动使用移位指令。