两个常见位操作面试题 不用加减乘除运算符计算两数之和及a=b*3

时间:2021-11-10 17:22:59

文章转自:http://blog.csdn.net/morewindows/article/details/8710737



《两个常见位操作面试题不用加减乘除运算符计算两数之和及a=b*3

地址:http://blog.csdn.net/morewindows/article/details/8710737转载请标明出处,谢谢。

欢迎关注微博:http://weibo.com/MoreWindows

 

上一篇《位操作基础篇之位操作全面总结》http://blog.csdn.net/morewindows/article/details/7354571)介绍了:

      一. 位操作基础,用一张表描述位操作符的应用规则并详细解释。

      二. 常用位操作小技巧,有判断奇偶、交换两数、变换符号、求绝对值。

      三. 位操作与空间压缩,针对筛素数进行空间压缩。

      四. 位操作的趣味应用,列举了位操作在高低位交换、二进制逆序、二进制中1的个数以及缺失的数字这4种趣味应用。

 

现在再来介绍两个位操作习题,这两个习题也常常在各大IT公司的笔试题面试题中出现。

1.不用加减乘除运算符计算两个数字之和

2.不用加减乘除运算符计算a = b * 3

 

首先这两个题目其实是很相关的,要计算

a = b * 3就是计算a = b *2 + ba = b << 1 + b

因此只要解决了不用加减乘除运算符计算两个数字之和,那么不用加减乘除运算符计算a = b * 3也就迎刃而解了。那么怎么不用加减乘除运算符计算两个数字之和了?我们知道在计算5 + 9时,首先不进位的话 5 + 9 = 45 + 9的进位为1,然后和就是1 * 10 + 4 = 14。同理放到二进制中也可以采用这样的方法。

运算步骤如下://By MoreWindows( http://blog.csdn.net/MoreWindows )

设有a = 3b = 6

a    0011

b    0110

不进位和 0101  = 5

进位         0010  = 2

因此 a + b就变成了5 + 2 << 1

然后有

5    0101

2<<1   0100

不进位和 0001  = 1

进位          0100  = 4

因此 a + b就变成了1 + 4 << 1

然后有

1    0001

4<<1   1000

不进位和 1001  = 9

进位          0000  = 0

当时进位为0时,不进位和为9a + b之和。

 

代码不难写出:

  1. //两个常见位操作面试题 不用加减乘除运算符计算两数之和及a=b*3   
  2. //http://blog.csdn.net/morewindows/article/details/8710737   
  3. //By MoreWindows( http://blog.csdn.net/MoreWindows )   
  4. #include <stdio.h>   
  5. #include <stdlib.h>   
  6. #include <time.h>   
  7. int BitAdd(int a, int b)  
  8. {  
  9.     int nCarry = a & b;      // 进位   
  10.     int nSumNoCarry = a ^ b; // 非进位   
  11.     if (nCarry != 0)  
  12.         return BitAdd(nSumNoCarry, nCarry << 1);  
  13.     else  
  14.         return nSumNoCarry;  
  15. }  
  16. int BitMultiplication3(int a)  
  17. {  
  18.     return BitAdd(a << 1, a);  
  19. }  
  20. int main()  
  21. {  
  22.     printf("   两个常见位操作面试题 不用加减乘除运算符计算两数之和及a=b*3\n");  
  23.     printf(" - http://blog.csdn.net/morewindows/article/details/8710737 -\n");  
  24.     printf(" - By MoreWindows( http://blog.csdn.net/MoreWindows - \n\n");  
  25.   
  26.   
  27.     srand(time(NULL));  
  28.     const int MAXNUMBER = 100;  
  29.     int a = rand() % MAXNUMBER, b = rand() % MAXNUMBER;  
  30.   
  31.     printf("\n      ------------------ 位操作之加法 --------------------\n");  
  32.     printf(" %d + %d = %d\n", a, b, BitAdd(a, b));  
  33.   
  34.     printf("\n      ------------------- 位操作之a = b * 3 -------------------\n");  
  35.     printf(" %d * 3 = %d\n", a, BitMultiplication3(a));  
  36.     return 0;  
  37. }  

运行结果如下所示:

两个常见位操作面试题 不用加减乘除运算符计算两数之和及a=b*3
 

《两个常见位操作面试题不用加减乘除运算符计算两数之和及a=b*3

地址:http://blog.csdn.net/morewindows/article/details/8710737转载请标明出处,谢谢。

欢迎关注微博:http://weibo.com/MoreWindows