如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
使用黑客的喜悦魔术数字计算器
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
其中fma是在math.h头文件中定义的标准库函数。
其他回答
愚蠢的情况需要愚蠢的解决方案:
#include <stdio.h>
#include <stdlib.h>
int main()
{
FILE * fp=fopen("temp.dat","w+b");
int number=12346;
int divisor=3;
char * buf = calloc(number,1);
fwrite(buf,number,1,fp);
rewind(fp);
int result=fread(buf,divisor,number,fp);
printf("%d / %d = %d", number, divisor, result);
free(buf);
fclose(fp);
return 0;
}
如果还需要小数部分,只需将result声明为double,并将fmod(number,除数)的结果添加到它。
解释它是如何工作的
fwrite写入number字节(在上面的例子中number为123456)。 “倒带”将文件指针重置到文件的前面。 Fread从文件中读取长度为除数的最多数量的“记录”,并返回它所读取的元素的数量。
如果你写30个字节,然后以3为单位读回文件,你会得到10个“单位”。30 / 3 = 10
哪里InputValue是数字除以3
SELECT AVG(NUM)
FROM (SELECT InputValue NUM from sys.dual
UNION ALL SELECT 0 from sys.dual
UNION ALL SELECT 0 from sys.dual) divby3
要将一个数除以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
}
第一:
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。
这是Python中的,基本上,字符串比较和一个状态机。
def divide_by_3(input):
to_do = {}
enque_index = 0
zero_to_9 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
leave_over = 0
for left_over in (0, 1, 2):
for digit in zero_to_9:
# left_over, digit => enque, leave_over
to_do[(left_over, digit)] = (zero_to_9[enque_index], leave_over)
if leave_over == 0:
leave_over = 1
elif leave_over == 1:
leave_over = 2
elif leave_over == 2 and enque_index != 9:
leave_over = 0
enque_index = (1, 2, 3, 4, 5, 6, 7, 8, 9)[enque_index]
answer_q = []
left_over = 0
digits = list(str(input))
if digits[0] == "-":
answer_q.append("-")
digits = digits[1:]
for digit in digits:
enque, left_over = to_do[(left_over, int(digit))]
if enque or len(answer_q):
answer_q.append(enque)
answer = 0
if len(answer_q):
answer = int("".join([str(a) for a in answer_q]))
return answer