如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
下面的脚本生成了一个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));
}
''')
其他回答
好吧,我想我们都同意这不是一个现实世界的问题。为了好玩,这里是如何用Ada和多线程来做这件事:
with Ada.Text_IO;
procedure Divide_By_3 is
protected type Divisor_Type is
entry Poke;
entry Finish;
private
entry Release;
entry Stop_Emptying;
Emptying : Boolean := False;
end Divisor_Type;
protected type Collector_Type is
entry Poke;
entry Finish;
private
Emptying : Boolean := False;
end Collector_Type;
task type Input is
end Input;
task type Output is
end Output;
protected body Divisor_Type is
entry Poke when not Emptying and Stop_Emptying'Count = 0 is
begin
requeue Release;
end Poke;
entry Release when Release'Count >= 3 or Emptying is
New_Output : access Output;
begin
if not Emptying then
New_Output := new Output;
Emptying := True;
requeue Stop_Emptying;
end if;
end Release;
entry Stop_Emptying when Release'Count = 0 is
begin
Emptying := False;
end Stop_Emptying;
entry Finish when Poke'Count = 0 and Release'Count < 3 is
begin
Emptying := True;
requeue Stop_Emptying;
end Finish;
end Divisor_Type;
protected body Collector_Type is
entry Poke when Emptying is
begin
null;
end Poke;
entry Finish when True is
begin
Ada.Text_IO.Put_Line (Poke'Count'Img);
Emptying := True;
end Finish;
end Collector_Type;
Collector : Collector_Type;
Divisor : Divisor_Type;
task body Input is
begin
Divisor.Poke;
end Input;
task body Output is
begin
Collector.Poke;
end Output;
Cur_Input : access Input;
-- Input value:
Number : Integer := 18;
begin
for I in 1 .. Number loop
Cur_Input := new Input;
end loop;
Divisor.Finish;
Collector.Finish;
end Divide_By_3;
为什么我们不直接用在大学里学过的定义呢?结果可能效率低,但很清楚,因为乘法只是递归的减法,减法是加法,那么加法可以通过递归的异或/和逻辑端口组合来执行。
#include <stdio.h>
int add(int a, int b){
int rc;
int carry;
rc = a ^ b;
carry = (a & b) << 1;
if (rc & carry)
return add(rc, carry);
else
return rc ^ carry;
}
int sub(int a, int b){
return add(a, add(~b, 1));
}
int div( int D, int Q )
{
/* lets do only positive and then
* add the sign at the end
* inversion needs to be performed only for +Q/-D or -Q/+D
*/
int result=0;
int sign=0;
if( D < 0 ) {
D=sub(0,D);
if( Q<0 )
Q=sub(0,Q);
else
sign=1;
} else {
if( Q<0 ) {
Q=sub(0,Q);
sign=1;
}
}
while(D>=Q) {
D = sub( D, Q );
result++;
}
/*
* Apply sign
*/
if( sign )
result = sub(0,result);
return result;
}
int main( int argc, char ** argv )
{
printf( "2 plus 3=%d\n", add(2,3) );
printf( "22 div 3=%d\n", div(22,3) );
printf( "-22 div 3=%d\n", div(-22,3) );
printf( "-22 div -3=%d\n", div(-22,-3) );
printf( "22 div 03=%d\n", div(22,-3) );
return 0;
}
有人说……首先让它工作。注意,该算法应该适用于负Q…
这是一个执行所需操作的简单函数。但是它需要+操作符,所以你所要做的就是用位操作符来加值:
// replaces the + operator
int add(int x, int y)
{
while (x) {
int t = (x & y) << 1;
y ^= x;
x = t;
}
return y;
}
int divideby3(int num)
{
int sum = 0;
while (num > 3) {
sum = add(num >> 2, sum);
num = add(num >> 2, num & 3);
}
if (num == 3)
sum = add(sum, 1);
return sum;
}
正如吉姆评论的那样,这是可行的,因为:
N = 4 * a + b N / 3 = a + (a + b) / 3 sum += an = a + b,然后迭代 当a == 0 (n < 4)时,sum += floor(n / 3);即1,如果n == 3,否则为0
这真的很简单。
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;
(当然,为了简洁起见,我省略了一些程序。)如果程序员厌倦了把这些都输入,我相信他或她可以编写一个单独的程序来为他生成这些。我碰巧认识一个能大大简化他工作的人。
在PHP中使用BC数学:
<?php
$a = 12345;
$b = bcdiv($a, 3);
?>
MySQL(来自Oracle的采访)
> SELECT 12345 DIV 3;
帕斯卡:
a:= 12345;
b:= a div 3;
X86-64汇编语言:
mov r8, 3
xor rdx, rdx
mov rax, 12345
idiv r8