如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
这是经典的2进制除法算法
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t mod3[6] = { 0,1,2,0,1,2 };
uint32_t x = 1234567; // number to divide, and remainder at the end
uint32_t y = 0; // result
int bit = 31; // current bit
printf("X=%u X/3=%u\n",x,x/3); // the '/3' is for testing
while (bit>0)
{
printf("BIT=%d X=%u Y=%u\n",bit,x,y);
// decrement bit
int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
uint32_t r = x>>bit; // current remainder in 0..5
x ^= r<<bit; // remove R bits from X
if (r >= 3) y |= 1<<bit; // new output bit
x |= mod3[r]<<bit; // new remainder inserted in X
}
printf("Y=%u\n",y);
}
其他回答
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int num = 1234567;
int den = 3;
div_t r = div(num,den); // div() is a standard C function.
printf("%d\n", r.quot);
return 0;
}
这真的很简单。
if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;
(当然,为了简洁起见,我省略了一些程序。)如果程序员厌倦了把这些都输入,我相信他或她可以编写一个单独的程序来为他生成这些。我碰巧认识一个能大大简化他工作的人。
我认为正确的答案是:
为什么不用基本运算符来做基本运算呢?
这在Setun电脑上很容易实现。
要把一个整数除3,右移1位。
不过,我不确定在这样的平台上是否有可能实现一个符合标准的C编译器。我们可能需要稍微扩展一下规则,比如将“至少8位”解释为“能够保存至少从-128到+127的整数”。
第一:
x/3 = (x/4) / (1-1/4)
然后求x/(1 - y)
x/(1-1/y)
= x * (1+y) / (1-y^2)
= x * (1+y) * (1+y^2) / (1-y^4)
= ...
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i)) / (1-y^(2^(i+i))
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i))
y = 1/4:
int div3(int x) {
x <<= 6; // need more precise
x += x>>2; // x = x * (1+(1/2)^2)
x += x>>4; // x = x * (1+(1/2)^4)
x += x>>8; // x = x * (1+(1/2)^8)
x += x>>16; // x = x * (1+(1/2)^16)
return (x+1)>>8; // as (1-(1/2)^32) very near 1,
// we plus 1 instead of div (1-(1/2)^32)
}
虽然它使用了+,但有人已经实现了按位操作的add。