如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
要将一个数除以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
}
其他回答
你可以使用(依赖于平台)内联程序集,例如,对于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;
}
要将一个32位数字除以3,可以将其乘以0x55555556,然后取64位结果的前32位。
现在剩下要做的就是使用位运算和移位来实现乘法…
并不是所有的答案都是面试官想听到的:
我的回答:
“我绝不会那样做,谁会为这种愚蠢的事情付出代价呢?”没有人 会有一个优势,它不是更快,它只是愚蠢。 教授设计师必须知道这一点,但这必须适用于所有数字,而不仅仅是除以3。”
第一:
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。
log(pow(exp(number),0.33333333333333333333)) /* :-) */