如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
这真的很简单。
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;
(当然,为了简洁起见,我省略了一些程序。)如果程序员厌倦了把这些都输入,我相信他或她可以编写一个单独的程序来为他生成这些。我碰巧认识一个能大大简化他工作的人。
其他回答
以下是我的解决方案:
public static int div_by_3(long a) {
a <<= 30;
for(int i = 2; i <= 32 ; i <<= 1) {
a = add(a, a >> i);
}
return (int) (a >> 32);
}
public static long add(long a, long b) {
long carry = (a & b) << 1;
long sum = (a ^ b);
return carry == 0 ? sum : add(carry, sum);
}
首先,请注意
1/3 = 1/4 + 1/16 + 1/64 + ...
现在,剩下的很简单!
a/3 = a * 1/3
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...
现在我们要做的就是把a的这些位移位值加在一起!哦!但是我们不能做加法,所以我们必须使用位操作符来编写一个加法函数!如果您熟悉逐位操作符,那么我的解决方案应该看起来相当简单……但以防你不懂,我会在最后讲一个例子。
另一件需要注意的事情是,首先我左移30!这是为了确保分数不会四舍五入。
11 + 6
1011 + 0110
sum = 1011 ^ 0110 = 1101
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100
Now you recurse!
1101 + 0100
sum = 1101 ^ 0100 = 1001
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000
Again!
1001 + 1000
sum = 1001 ^ 1000 = 0001
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000
One last time!
0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17
carry = (0001 & 10000) << 1 = 0
Done!
这就是你小时候学过的简单加法!
111
1011
+0110
-----
10001
这个实现失败了,因为我们不能把方程的所有项相加:
a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i
假设div_by_3(a) = x的结果,则x <= floor(f(a, i)) < a / 3。当a = 3k时,我们得到错误的答案。
你可以使用(依赖于平台)内联程序集,例如,对于x86:(也适用于负数)
#include <stdio.h>
int main() {
int dividend = -42, divisor = 5, quotient, remainder;
__asm__ ( "cdq; idivl %%ebx;"
: "=a" (quotient), "=d" (remainder)
: "a" (dividend), "b" (divisor)
: );
printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder);
return 0;
}
使用黑客的喜悦魔术数字计算器
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
其中fma是在math.h头文件中定义的标准库函数。
使用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
}
没有反复检查这个答案是否已经发表。如果程序需要扩展到浮点数,可以将这些数字乘以所需精度的10*数,然后可以再次应用下面的代码。
#include <stdio.h>
int main()
{
int aNumber = 500;
int gResult = 0;
int aLoop = 0;
int i = 0;
for(i = 0; i < aNumber; i++)
{
if(aLoop == 3)
{
gResult++;
aLoop = 0;
}
aLoop++;
}
printf("Reulst of %d / 3 = %d", aNumber, gResult);
return 0;
}