如何将一个数除3而不使用*、/、+、-、%等运算符?

号码可以有签名,也可以没有签名。


当前回答

这真的很简单。

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;

(当然,为了简洁起见,我省略了一些程序。)如果程序员厌倦了把这些都输入,我相信他或她可以编写一个单独的程序来为他生成这些。我碰巧认识一个能大大简化他工作的人。

其他回答

很有趣的是,没有人回答一个泛泛的划分:

/* For the given integer find the position of MSB */
int find_msb_loc(unsigned int n)
{
    if (n == 0)
        return 0;

    int loc = sizeof(n)  * 8 - 1;
    while (!(n & (1 << loc)))
        loc--;
    return loc;
}


/* Assume both a and b to be positive, return a/b */
int divide_bitwise(const unsigned int a, const unsigned int b)
{
    int int_size = sizeof(unsigned int) * 8;
    int b_msb_loc = find_msb_loc(b);

    int d = 0; // dividend
    int r = 0; // reminder
    int t_a = a;
    int t_a_msb_loc = find_msb_loc(t_a);
    int t_b = b << (t_a_msb_loc - b_msb_loc);

    int i;
    for(i = t_a_msb_loc; i >= b_msb_loc; i--)  {
        if (t_a > t_b) {
            d = (d << 1) | 0x1;
            t_a -= t_b; // Not a bitwise operatiion
            t_b = t_b >> 1;
         }
        else if (t_a == t_b) {
            d = (d << 1) | 0x1;
            t_a = 0;
        }
        else { // t_a < t_b
            d = d << 1;
            t_b = t_b >> 1;
        }
    }

    r = t_a;
    printf("==> %d %d\n", d, r);
    return d;
}

按位加法已经在其中一个答案中给出,所以跳过它。

我认为正确的答案是:

为什么不用基本运算符来做基本运算呢?

这是经典的2进制除法算法

#include <stdio.h>
#include <stdint.h>

int main()
{
  uint32_t mod3[6] = { 0,1,2,0,1,2 };
  uint32_t x = 1234567; // number to divide, and remainder at the end
  uint32_t y = 0; // result
  int bit = 31; // current bit
  printf("X=%u   X/3=%u\n",x,x/3); // the '/3' is for testing

  while (bit>0)
  {
    printf("BIT=%d  X=%u  Y=%u\n",bit,x,y);
    // decrement bit
    int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
    uint32_t r = x>>bit;  // current remainder in 0..5
    x ^= r<<bit;          // remove R bits from X
    if (r >= 3) y |= 1<<bit; // new output bit
    x |= mod3[r]<<bit;    // new remainder inserted in X
  }
  printf("Y=%u\n",y);
}

似乎没有人提到用二进制表示的3的除法准则——偶数的和应该等于奇数的和(类似于十进制中11的准则)。在“检查一个数是否能被3整除”一栏中有使用这个技巧的解决方案。

我想这就是迈克尔·伯尔的编辑提到的可能的复制品。

使用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