如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
一般来说,解决这个问题的方法是:
log(pow(exp(numerator),pow(deliminator,-1)))
其他回答
下面的脚本生成了一个C程序,可以在不使用运算符* / + - %的情况下解决这个问题:
#!/usr/bin/env python3
print('''#include <stdint.h>
#include <stdio.h>
const int32_t div_by_3(const int32_t input)
{
''')
for i in range(-2**31, 2**31):
print(' if(input == %d) return %d;' % (i, i / 3))
print(r'''
return 42; // impossible
}
int main()
{
const int32_t number = 8;
printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')
这真的很简单。
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;
(当然,为了简洁起见,我省略了一些程序。)如果程序员厌倦了把这些都输入,我相信他或她可以编写一个单独的程序来为他生成这些。我碰巧认识一个能大大简化他工作的人。
我会用这段代码除所有正数,非浮点数。基本上你要把除数位向左对齐以匹配被除数位。对于被除数的每一段(除数的大小),你想要检查是否被除数的每一段大于除数,然后你想要左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
要将一个数除以3,而不使用乘法、除法、余数、减法或加法操作,在汇编编程语言中,惟一可用的指令是LEA(地址有效负载)、SHL(向左移动)和SHR(向右移动)。
在这个解决方案中,我没有使用与运算符+ - * /%相关的操作
我假设有输出数字在定点格式(16位整数部分和16位小数部分)和输入数字的类型是短int;但是,我已经近似输出的数量,因为我只能信任整数部分,因此我返回一个短int类型的值。
65536/6是固定点值,相当于1/3浮点数,等于21845。
21845 = 16384 + 4096 + 1024 + 256 + 64 + 16 + 4 + 1.
因此,要用1/3(21845)来做乘法,我使用指令LEA和SHL。
short int DivideBy3( short int num )
//In : eax= 16 Bit short int input number (N)
//Out: eax= N/3 (32 Bit fixed point output number
// (Bit31-Bit16: integer part, Bit15-Bit0: digits after comma)
{
__asm
{
movsx eax, num // Get first argument
// 65536 / 3 = 21845 = 16384 + 4096 + 1024 + 256 + 64 + 16 + 4 + 1
lea edx,[4*eax+eax] // EDX= EAX * 5
shl eax,4
lea edx,[eax+edx] // EDX= EDX + EAX * 16
shl eax,2
lea edx,[eax+edx] // EDX= EDX + EAX * 64
shl eax,2
lea edx,[eax+edx] // EDX= EDX + EAX * 256
shl eax,2
lea edx,[eax+edx] // EDX= EDX + EAX * 1024
shl eax,2
lea edx,[eax+edx] // EDX= EDX + EAX * 4096
shl eax,2
lea edx,[eax+edx+08000h] // EDX= EDX + EAX * 16384
shr edx,010h
movsx eax,dx
}
// Return with result in EAX
}
它也适用于负数;结果具有正数的最小近似值(逗号后的最后一位数字为-1)。
如果您不打算使用运算符+ - * /%来执行除3的操作,但可以使用与它们相关的操作,我建议另一种解决方案。
int DivideBy3Bis( short int num )
//In : eax= 16 Bit short int input number (N)
//Out: eax= N/3 (32 Bit fixed point output number
// (Bit31-Bit16: integer part, Bit15-Bit0: digits after comma)
{
__asm
{
movsx eax, num // Get first argument
mov edx,21845
imul edx
}
// Return with result in EAX
}
使用fma()库函数的解决方案,适用于任何正数:
#include <stdio.h>
#include <math.h>
int main()
{
int number = 8;//Any +ve no.
int temp = 3, result = 0;
while(temp <= number){
temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
result = fma(result, 1, 1);
}
printf("\n\n%d divided by 3 = %d\n", number, result);
}
请看我的另一个答案。