如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
很好bc:
$ num=1337; printf "scale=5;${num}\x2F3;\n" | bc
445.66666
其他回答
我会用这段代码除所有正数,非浮点数。基本上你要把除数位向左对齐以匹配被除数位。对于被除数的每一段(除数的大小),你想要检查是否被除数的每一段大于除数,然后你想要左Shift,然后在第一个注册器中OR。这个概念最初是在2004年创建的(我相信是斯坦福大学),这里是一个C版本,它使用了这个概念。注:(我做了一点修改)
int divide(int a, int b)
{
int c = 0, r = 32, i = 32, p = a + 1;
unsigned long int d = 0x80000000;
while ((b & d) == 0)
{
d >>= 1;
r--;
}
while (p > a)
{
c <<= 1;
p = (b >> i--) & ((1 << r) - 1);
if (p >= a)
c |= 1;
}
return c; //p is remainder (for modulus)
}
使用示例:
int n = divide( 3, 6); //outputs 2
使用itoa转换为以3为基数的字符串。去掉最后一个小调,转换回10进制。
// Note: itoa is non-standard but actual implementations
// don't seem to handle negative when base != 10.
int div3(int i) {
char str[42];
sprintf(str, "%d", INT_MIN); // Put minus sign at str[0]
if (i>0) // Remove sign if positive
str[0] = ' ';
itoa(abs(i), &str[1], 3); // Put ternary absolute value starting at str[1]
str[strlen(&str[1])] = '\0'; // Drop last digit
return strtol(str, NULL, 3); // Read back result
}
(注意:查看下面的编辑2以获得更好的版本!)
这并不像听起来那么棘手,因为你说“没有使用[..+[…]运营商”。如果你想禁止同时使用+字符,请参见下面。
unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
for (unsigned i = 0; i < by; i++)
cmp++; // that's not the + operator!
floor = r;
r++; // neither is this.
}
return floor;
}
然后用div_by(100,3)将100除以3。
编辑:你可以继续并替换++操作符:
unsigned inc(unsigned x) {
for (unsigned mask = 1; mask; mask <<= 1) {
if (mask & x)
x &= ~mask;
else
return x & mask;
}
return 0; // overflow (note that both x and mask are 0 here)
}
编辑2:稍快的版本,不使用任何包含+、-、*、/、%字符的操作符。
unsigned add(char const zero[], unsigned const x, unsigned const y) {
// this exploits that &foo[bar] == foo+bar if foo is of type char*
return (int)(uintptr_t)(&((&zero[x])[y]));
}
unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
cmp = add(0,cmp,by);
floor = r;
r = add(0,r,1);
}
return floor;
}
我们使用add函数的第一个参数,因为不使用*字符就不能表示指针的类型,除非在函数形参列表中,其中的语法类型[]与类型* const相同。
FWIW,你可以很容易地实现一个乘法函数使用类似的技巧使用0x55555556技巧提出的AndreyT:
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
第一:
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。
int div3(int x)
{
int reminder = abs(x);
int result = 0;
while(reminder >= 3)
{
result++;
reminder--;
reminder--;
reminder--;
}
return result;
}