牛客剑指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);}