如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
这在Setun电脑上很容易实现。
要把一个整数除3,右移1位。
不过,我不确定在这样的平台上是否有可能实现一个符合标准的C编译器。我们可能需要稍微扩展一下规则,比如将“至少8位”解释为“能够保存至少从-128到+127的整数”。
其他回答
使用cblas,作为OS X加速框架的一部分。
[02:31:59] [william@relativity ~]$ cat div3.c
#import <stdio.h>
#import <Accelerate/Accelerate.h>
int main() {
float multiplicand = 123456.0;
float multiplier = 0.333333;
printf("%f * %f == ", multiplicand, multiplier);
cblas_sscal(1, multiplier, &multiplicand, 1);
printf("%f\n", multiplicand);
}
[02:32:07] [william@relativity ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031
#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;
}
以下是我的解决方案:
public static int div_by_3(long a) {
a <<= 30;
for(int i = 2; i <= 32 ; i <<= 1) {
a = add(a, a >> i);
}
return (int) (a >> 32);
}
public static long add(long a, long b) {
long carry = (a & b) << 1;
long sum = (a ^ b);
return carry == 0 ? sum : add(carry, sum);
}
首先,请注意
1/3 = 1/4 + 1/16 + 1/64 + ...
现在,剩下的很简单!
a/3 = a * 1/3
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...
现在我们要做的就是把a的这些位移位值加在一起!哦!但是我们不能做加法,所以我们必须使用位操作符来编写一个加法函数!如果您熟悉逐位操作符,那么我的解决方案应该看起来相当简单……但以防你不懂,我会在最后讲一个例子。
另一件需要注意的事情是,首先我左移30!这是为了确保分数不会四舍五入。
11 + 6
1011 + 0110
sum = 1011 ^ 0110 = 1101
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100
Now you recurse!
1101 + 0100
sum = 1101 ^ 0100 = 1001
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000
Again!
1001 + 1000
sum = 1001 ^ 1000 = 0001
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000
One last time!
0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17
carry = (0001 & 10000) << 1 = 0
Done!
这就是你小时候学过的简单加法!
111
1011
+0110
-----
10001
这个实现失败了,因为我们不能把方程的所有项相加:
a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i
假设div_by_3(a) = x的结果,则x <= floor(f(a, i)) < a / 3。当a = 3k时,我们得到错误的答案。
为什么我们不直接用在大学里学过的定义呢?结果可能效率低,但很清楚,因为乘法只是递归的减法,减法是加法,那么加法可以通过递归的异或/和逻辑端口组合来执行。
#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…
如果我们认为__div__不是正字法上的/
def divBy3(n):
return n.__div__(3)
print divBy3(9), 'or', 9//3