如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
使用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
}
其他回答
使用黑客的喜悦魔术数字计算器
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
其中fma是在math.h头文件中定义的标准库函数。
很好bc:
$ num=1337; printf "scale=5;${num}\x2F3;\n" | bc
445.66666
你可以使用(依赖于平台)内联程序集,例如,对于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 DivBy3(int num) {
int result = 0;
int counter = 0;
while (1) {
if (num == counter) //Modulus 0
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 1
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 2
return result;
counter = abs(~counter); //++counter
result = abs(~result); //++result
}
}
也很容易执行一个模数函数,查看注释。
如果你提醒自己标准的学校除法方法,用二进制来做,你会发现在3的情况下,你只是在有限的一组值中除法和减法(在这种情况下,从0到5)。这些可以用switch语句处理,以摆脱算术运算符。
static unsigned lamediv3(unsigned n)
{
unsigned result = 0, remainder = 0, mask = 0x80000000;
// Go through all bits of n from MSB to LSB.
for (int i = 0; i < 32; i++, mask >>= 1)
{
result <<= 1;
// Shift in the next bit of n into remainder.
remainder = remainder << 1 | !!(n & mask);
// Divide remainder by 3, update result and remainer.
// If remainder is less than 3, it remains intact.
switch (remainder)
{
case 3:
result |= 1;
remainder = 0;
break;
case 4:
result |= 1;
remainder = 1;
break;
case 5:
result |= 1;
remainder = 2;
break;
}
}
return result;
}
#include <cstdio>
int main()
{
// Verify for all possible values of a 32-bit unsigned integer.
unsigned i = 0;
do
{
unsigned d = lamediv3(i);
if (i / 3 != d)
{
printf("failed for %u: %u != %u\n", i, d, i / 3);
return 1;
}
}
while (++i != 0);
}