牛客剑指offer刷题位运算篇

不用加减乘除做加法

题目

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:
输入: a = 1, b = 1
输出: 2

提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数
LeetCode链接

思路

采用位运算思想：
a ^ b 的结果为 a+b 二进制运算不进位的情况；
a & b 的结果为 a+b 二进制运算进位的情况，当发生进位操作时，使用<< 1位即可；
通过不断 ^ & 操作判断是否仍然需要进位，直到不需要进位时，即可得到最终结果
LeetCode解题思路

代码实现

 public int add(int a, int b) {
        int m = a ^ b;  //用于表示相加结果
        int n = (a & b) << 1; //表示进位
        while(n != 0){
            int temp = m ^ n;
            n = (m & n) << 1;
            m = temp;
        }
        return m;
    }

二进制中1的个数

题目

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
LeetCode链接

思路

我们知道:
若 a & 1 = 1 说明a最后一位是1，如果为0，说明最后一位是0；
因此我们可以通过不断进行右移操作，判断a最后一位是否为1从而进行累加计算；
由于本题输出的是无符号整数，对应的应该使用无符号右移，对应 >>>

代码实现

 public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            res += n & 1;
            n = n >>> 1;
        }
        return res;
    }

数值的整数次方

题目

描述
实现函数 double Power(double base, int exponent)，求base的exponent次方。

注意：
1.保证base和exponent不同时为0。
2.不得使用库函数，同时不需要考虑大数问题
3.有特殊判题，不用考虑小数点后面0的位数。

示例1
输入：
2.00000,3
返回值：
8.00000

示例2
输入：
2.10000,3
返回值：
9.26100

示例3
输入：
2.00000,-2
返回值：
0.25000
说明：
2的-2次方等于1/4=0.25

牛客题目链接

思路

首先需要对exponent为负数的情况进行处理，也就对应(1/base)^（-exponent）；
然后采用递归的思想，将计算base^exponent分解为求 base^(exponent/2) * base^(exponent - exponent/2),而exponent/2最终结果不是为0就是为1，即可以轻松计算出结果；

代码实现

 public double Power(double base, int exponent) {
 		//首先判断exponent是正数还是负数
        return exponent > 0 ? quickPower(base,exponent) :quickPower(1/base,-exponent); 
  }

  private double quickPower(double base, int exponent){
        if(exponent == 0){
            return 1;
        }
        if(exponent == 1){
            return base;
        }
        //递归求解
        return quickPower(base,exponent/2) * quickPower(base, exponent - exponent/2);
  }