如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
这应该适用于任何除数,而不仅仅是3。目前仅适用于unsigned,但将其扩展到signed应该没有那么困难。
#include <stdio.h>
unsigned sub(unsigned two, unsigned one);
unsigned bitdiv(unsigned top, unsigned bot);
unsigned sub(unsigned two, unsigned one)
{
unsigned bor;
bor = one;
do {
one = ~two & bor;
two ^= bor;
bor = one<<1;
} while (one);
return two;
}
unsigned bitdiv(unsigned top, unsigned bot)
{
unsigned result, shift;
if (!bot || top < bot) return 0;
for(shift=1;top >= (bot<<=1); shift++) {;}
bot >>= 1;
for (result=0; shift--; bot >>= 1 ) {
result <<=1;
if (top >= bot) {
top = sub(top,bot);
result |= 1;
}
}
return result;
}
int main(void)
{
unsigned arg,val;
for (arg=2; arg < 40; arg++) {
val = bitdiv(arg,3);
printf("Arg=%u Val=%u\n", arg, val);
}
return 0;
}
其他回答
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int num = 1234567;
int den = 3;
div_t r = div(num,den); // div() is a standard C function.
printf("%d\n", r.quot);
return 0;
}
log(pow(exp(number),0.33333333333333333333)) /* :-) */
要将一个数除以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
}
我会用这段代码除所有正数,非浮点数。基本上你要把除数位向左对齐以匹配被除数位。对于被除数的每一段(除数的大小),你想要检查是否被除数的每一段大于除数,然后你想要左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的数一样多。然后继续将每个未配对的顶点与其他两个顶点配对。
粗糙的伪代码:
function divide(int num)
while(num!=0)
Add a new vertice to vertiexList.
num--
quotient = 0
for each in vertexList(lets call this vertex A)
if vertexList not empty
Add an edge between A and another vertex(say B)
else
your Remainder is 1 and Quotient is quotient
if vertexList not empty
Add an edge between A and another vertex(say C)
else
your remainder is 2 and Quotient is quotient
quotient++
remove A, B, C from vertexList
Remainder is 0 and Quotient is quotient
这显然是可以优化的,复杂度取决于你的数字有多大,但它应该工作,只要你能做++和——。 这就像数更酷的东西一样。