如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
这是可行的:
smegma$ curl http://www.wolframalpha.com/input/?i=14+divided+by+3 2>/dev/null | gawk 'match($0, /link to /input/\?i=([0-9.+-]+)/, ary) { print substr( $0, ary[1, "start"], ary[1, "length"] )}' 4.6666666666666666666666666666666666666666666666666666
只要把你的数字换成“14”和“3”就行了。
其他回答
使用Linux shell脚本:
#include <stdio.h>
int main()
{
int number = 30;
char command[25];
snprintf(command, 25, "echo $((%d %c 3)) ", number, 47);
system( command );
return 0;
}
请看我的另一个答案。
(注意:查看下面的编辑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。
并不是所有的答案都是面试官想听到的:
我的回答:
“我绝不会那样做,谁会为这种愚蠢的事情付出代价呢?”没有人 会有一个优势,它不是更快,它只是愚蠢。 教授设计师必须知道这一点,但这必须适用于所有数字,而不仅仅是除以3。”
要将一个32位数字除以3,可以将其乘以0x55555556,然后取64位结果的前32位。
现在剩下要做的就是使用位运算和移位来实现乘法…