如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名，也可以没有签名。
当前回答
以下是我的解决方案:
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时，我们得到错误的答案。
其他回答
Yet another solution. This should handle all ints (including negative ints) except the min value of an int, which would need to be handled as a hard coded exception. This basically does division by subtraction but only using bit operators (shifts, xor, & and complement). For faster speed, it subtracts 3 * (decreasing powers of 2). In c#, it executes around 444 of these DivideBy3 calls per millisecond (2.2 seconds for 1,000,000 divides), so not horrendously slow, but no where near as fast as a simple x/3. By comparison, Coodey's nice solution is about 5 times faster than this one.
public static int DivideBy3(int a) {
bool negative = a < 0;
if (negative) a = Negate(a);
int result;
int sub = 3 << 29;
int threes = 1 << 29;
result = 0;
while (threes > 0) {
if (a >= sub) {
a = Add(a, Negate(sub));
result = Add(result, threes);
}
sub >>= 1;
threes >>= 1;
}
if (negative) result = Negate(result);
return result;
}
public static int Negate(int a) {
return Add(~a, 1);
}
public static int Add(int a, int b) {
int x = 0;
x = a ^ b;
while ((a & b) != 0) {
b = (a & b) << 1;
a = x;
x = a ^ b;
}
return x;
}
这是c#，因为这是我手边的东西，但与c的区别应该很小。
以下是我的解决方案:
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时，我们得到错误的答案。
如果你提醒自己标准的学校除法方法，用二进制来做，你会发现在3的情况下，你只是在有限的一组值中除法和减法(在这种情况下，从0到5)。这些可以用switch语句处理，以摆脱算术运算符。
static unsigned lamediv3(unsigned n)
{
unsigned result = 0, remainder = 0, mask = 0x80000000;
// Go through all bits of n from MSB to LSB.
for (int i = 0; i < 32; i++, mask >>= 1)
{
result <<= 1;
// Shift in the next bit of n into remainder.
remainder = remainder << 1 | !!(n & mask);
// Divide remainder by 3, update result and remainer.
// If remainder is less than 3, it remains intact.
switch (remainder)
{
case 3:
result |= 1;
remainder = 0;
break;
case 4:
result |= 1;
remainder = 1;
break;
case 5:
result |= 1;
remainder = 2;
break;
}
}
return result;
}
#include <cstdio>
int main()
{
// Verify for all possible values of a 32-bit unsigned integer.
unsigned i = 0;
do
{
unsigned d = lamediv3(i);
if (i / 3 != d)
{
printf("failed for %u: %u != %u\n", i, d, i / 3);
return 1;
}
}
while (++i != 0);
}
使用计数器是一个基本的解决方案:
int DivBy3(int num) {
int result = 0;
int counter = 0;
while (1) {
if (num == counter) //Modulus 0
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 1
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 2
return result;
counter = abs(~counter); //++counter
result = abs(~result); //++result
}
}
也很容易执行一个模数函数，查看注释。
3以2为底等于11。
所以只要做长除法(就像中学那样)，以2 × 11为底。以2为底比以10为底更简单。
对于从最有效位开始的每个位位:
判断prefix是否小于11。
如果它是输出0。
如果不是输出1，则替换前缀位进行适当的更改。只有三种情况:
11xxx -> xxx (ie 3 - 3 = 0)
100xxx -> 1xxx (ie 4 - 3 = 1)
101xxx -> 10xxx (ie 5 - 3 = 2)
所有其他前缀都不可达。
重复到最低位，你就完成了。
