华为的一道笔试题！大家看看该如何做！

做函数int f(int a),该函数的功能是求出a除以3的余数；
要求：在函数中只能用+、-、*、>>号完成，不能用/和%！

41 个解决方案

#1

mark

#2

up

#3

同意 luanjiajia(抵制日货,从我做起) ，  经典的除法/余数 是用（移位-比较-减法）来实现的，如果仅仅是除以3， 最快的算法是事先造一张表，内容为 3， 3*2， 3*2^2,...
,这样只需要比较和减法运算，速度很快。
  如果在 x86(386 以上）用vc 编成，速度最开的算法是是： 
 
  DWORD f(DWORD a)
  {
     _asm
    {
       mov eax,a
       mov ebx,1431655765
       mul eax,edx  

       mov eax,edx
       shl edx,1  
       add eax,edx  ; eax=edx*3

       sub eax,a ; 余数
       cmp eax,3
       jb next
       sub eax,3
     next:
     }
  }
  请高手验证其正确性，如果没有问题，请指出其原理，如果有问题，指出问题所在。

#4

抱歉：刚才的代码没有调试，有错误，这里给出正确的代码和测试程序。

#include "stdafx.h"
#include "math.h"
#include "stdlib.h"
typedef unsigned long DWORD;

DWORD f1( DWORD  a)
{ return a % 3; }

DWORD  f2(DWORD a)
{
   _asm
  {
    mov eax,a
    mov ebx,1431655765
    mul ebx  
 
    mov eax,edx
    shl edx,1  
    add edx,eax  ; edx=edx*3
 
    mov eax,a
    sub eax,edx ; 余数
 
    cmp eax,3
    jb next
    sub eax,3
next:
     }
}

int main(int argc, char* argv[])
{
   DWORD a,b1,b2;
   for (int i=0;i<1000;i++)
   {
      a=rand();
      if (a <=0)
continue;
      b1=f1(a); b2=f2(a);
      if (b1!=b2)
{printf("%d mod %d, right=%d, wrong=%d \n", a,3,b1,b2); }
   }
   return 0;
}

#5

将这个函数中，汇编指令减小，不然会吓跑出学者的

DWORD f(DWORD a)
{
   DWORD tmp,m;

     _asm
    {
       mov eax,a
       mov ebx,1431655765
       mul ebx  
       mov tmp,edx   
    }
    m=a-(tmp+tmp+tmp);     
    if (m>3)
      m-=3;
    return tmp;
}

#6

一直减3到负数。。。

#7

up

#8

这个帖子应该移动专题开发-数据结构与算法板。

#9

其实这仅仅是一个进制的问题，简单的想，就是十进制要除以3，就是2进制要除以11，任何一个数字转化为2进制后只要二进制里面全是以“11”和“0”组合的数，就是能被3整除的。
具体算法为：
    从高位开始，二进制数中所有的“11”替换为“00”，然后如果得到的二进制数为一个小于“11”即“3”的整数，则此整数为余数，否则将所得的数减去一个“11”，即减去“3”，所得的数再进行前面的“将‘11’用‘00’替换”的操作，直到得到最终的一个小于“11”即“3”的整数。

#10

别去华为！！！

#11

mark

#12

一群菜鸟 —— —……%￥#·！（
不要砸鸡蛋

我只提供一种数学算法，程序各位再写
任何一数：如223569除以3余为多少
应这样算2+2+3+5+6+9=27
        27再分2+7=9
OK 223569除以3余0

明白了吗 
再试一个：55889632547125639
                  5+5+8+8+9+6+3+2+5+4+7+1+2+5+6+3+9=89
                  89  分8+9=17
                  17  分1+7=8
 OK    55889632547125639  除以3应余2。

这样思考才有可能是最佳算法，最佳算法都要建立在数学上
正入算10000000的阶乘一样
盲目的傻算，只能是等到地球的终结也算不完
///////////////////////////////////////////
切，也不用叫别人菜鸟阿,出的这题顶多是小学4年级左右的题目，
中国软件人员的培训就是被这些不伦不类的什么考题（小学奥数经常用到的题）给弄砸了，
瞎狗屁教育

#13

up

#14

怎么越搞越复杂，I服your!!

#15

用>>移位运算就行了

#16

怎么没有人对我的程序点评呀，看来来这里的大多数是菜鸟。
  1。使用 多次循环（比较-移位-相减）应该是通常的做法，速度不是最快，也不会慢的那儿去。
  2。至于一直减到3以内，算法虽然简单，速度太慢，不合题目要求。
  3。godblood(老邪) 请看仔细了，题目要求的函数的入参为整数，将一个整数，转化为10进制数本身就需要大量的除法运算，这违反了 不能使用乘法的要求。
  4。to  yichunhui(塘坊),你的算法好像有问题，按照你的解法，1011b(10进制11) 除以3余数为何？
  5。从计算速度上讲，我认为，我的程序速度最快，没有使用循环，只用了1个乘法指令。

#17

去华为可以赚钱，呵呵
但是我坚决不去，因为那个地方不能上网，不能看csdn

#18

up

#19

哎..都是写得什么呀..看不懂..

#20

a可以为负数的，老实说，我到现在还不确定负数的余数怎么算的！
余数的标准定义是什么：必须比除数小？

#21

华为是做交换机的，出这样的题不算过分

#22

int f(int a)
{
   return (a - ((a >> 2) * 4));
}

最简单吧;

#23

我想华为要的就是这个答案

想想: 一个数除以3,只能余 0 , 1, 2
而0,1,2只要两个二进制数就能表示
所以余数一定是a的二进制数的最低二位了,就只要想办法取出最低二位

(a - ((a >> 2) * 4))就达到要求

#24

不好意思,搞错了,这是求4的余数

#25

up

#26

真气人,只能连续回三次,等了半天

可以把上面改进一下,最简单最快的代码了

int f(int a)
{
   int temp = (a - ((a >> 2) * 4));

   return ((temp == 3) ? 0 : temp);
}

这个可以了,唉,真是太粗心了.

#27

我自杀去了,根本就是一个错误,呵呵,今天是愚人节嘛

#28

这种绝对是最优代码:
f(int a)
{ 
  if (a < 3 )
         return a;
  a = a - 3;
  f(a);

}

#29

这么多高手呀

#30

int f(int a){
   int tmp = a&1;//取最后一位
   int tmp2 = (a>>1)&1;
   return tmp2*2+tmp1;
}

#31

发错了

#32

只能+、-、*、>>,没有/,%,用什么算法拆分5888888,为5,8,8,8,8,8,8,8?

#33

这就是中国人的恶俗无聊！

这就是为什么中国人的数学素质极高，但是科技仍旧落后的原因：

                      中国人喜欢人玩人！

#34

不好意思,是我出的,我只想考考求职者的正常智商

#35

昏，用位移就可以实现了！

#36

苦,同样的命运将会落在我的头上啦。

#37

fun(int a)
{  int i = 1;
  int a
  do while a < 3
     a =-3;
  loop
  return a;
}

#38

如何位移？呵呵。

#39

while( (a=(a-(a>>2)*3)) > 3)
     a=a-(a>>2)*3;
if(a==3)
     a=0;

#40

if a>3 while (a<=3) a-=3;return a;

#41

有分就不能错过！