奇妙的位运算

世界上有10种人，一种懂二进制，另一种不懂二进制。

原码：最高位为符号位，其余为数值本身的绝对值 反码：当值为正数时，与原码相同；当为负数时，符号位为1，其余位置取反原码（按位取反） 补码：当数值为正数时，与原码相同；当为负数时，符号位为1，其余位置反向原码，然后反向整个数 1，即反码 1.负数补码原码=补码的反码 1

?? 举例： 为了整洁，这里有一个字节，即8个比特表示二进制数。由于最高位为符号位，1字节能表示的十进制数范围为-127-127

计算机数字运算是基于补码的。

注：该方法仅适用于十进制正整数

parseInt(127).toString(2) ---> 1111111 parseInt(43).toString(2) ---> 101011 

常见的位运算符有：与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>带符号右移 >>>右移动无符号)

1. 位与（&）：当两者都是1时，结果是1
2. 位或（|）：当两者都是0时，结果是0
3. 异或（^）: 当两者不同时，结果是1
4. 取反（~）：按位取反，0->1, 1->0
5. 左移（<<）: 放弃高位，补低位 0
6. 右移（>>）: 低位放弃，高位正数补充 0.负数补充1(负数右移操作时，在右移操作前请求负数原码补充)

在数字不溢出的前提下，正负： 左移一位相当于乘以2的一次方，左移n位相当于乘以2的n次方； 右移一位相当于2向下取整，右移n位相当于2n次取整。

?? 举例：

1. 设置x的第n位为1

	x | (1<<n)

2. 设置x的第n位为0

	x & ~(1<<n)

3. 将x的第n位取反

	x ^ (1<<n)

4. 得到最大的int

	int maxInt = ~(1 << 31);
	int maxInt = (1 << 31) - 1;
	int maxInt = (1 << -1) - 1;

5. 到最小的int

	int minInt = 1 << 31;
	int minInt = 1 << -1;

6. 计算n乘以2

	n << 1

7. 计算n除以2

	n >> 1

8. 计算n乘以2的m次方

	n << m

9. 就算n除以2的m次方

	n >> m

10. 判断a和b是否相等

	!(a^b)

11. 判断n是否为奇数

	(n & 1) == 1

12. 交换a和b的值

	//方式1
	a ^= b;
	b ^= a;
	a ^= b;
	//方式2
	a = a ^ b ^ (b = a)

13. 得到x的绝对值

	(x ^ (x >> 31)) - (x >> 31)

14. 得到a和b中较大的数

	b & ((a-b) >> 31) | a & (~(a-b) >> 31)

15. 得到a和b中较小的数

	a & ((a-b) >> 31) | b & (~(a-b) >> 31)

16. 判断a和b是否同正负

	(x ^ y) >= 0

17. 计算i的相反数

	//方式1
	i = ~i + 1
	//方式2
	i = (i ^ -1) + 1

18. 判断n是否为2的若干次方

	n > 0 && (n & (n - 1)) == 0

19. 拿到x的位于最右的1位

	x & (-x)

20. 拿到x的位于最右的0位

	~x & (x+1)

21. 将x的位于最右的0位设置为1

	x | (x+1)

22. 计算n + 1

	-~n

23. 计算n - 1

	~-n

24. 将x(x为字符)转换为小写(如果原来就已经为小写则保持)

	x | ' '

25. 将x(x为字符)转换为大写(如果原来就已经为大写则保持)

	x & '_'

26. 大小写互换(x为字符)

	x ^ ' '

27. 得到x(x为字符)在字母表中的位置(大小写都适用)

	x & '\x1F'

1.【2的幂】

给定一个整数n，如果它是2的幂，则返回true，否则返回false ——【leetCode 231】

题目分析：如果是2的幂，则这个数一定大于等于0，并且转化为二进制数必然为1后面加若干个0。假设为1000，那么1000 - 1 = 0001。那么这个整数n满足： n & (n-1) = 0;

题解：

/** * @param {number} n * @return {boolean} */
var isPowerOfTwo = function(n) { 
        
    return (n > 0 && (n & (n-1)) === 0)
};

2.【4的幂】

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。 ——【leetCode 342】

题目分析：4^x = 2^2x， 4的幂一定是2的幂，但是2的幂不一定是4的。 推理可得： 2^2x % 3 = 1; 2^2x+1 % 3 = 2;

题解：

/** * @param {number} n * @return {boolean} */
var isPowerOfFour = function(n) { 
        
    return n > 0 && (n & (n-1)) === 0 && n % 3 === 1
};

3.【位1的个数】

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

题目分析：二进制n 不断的位与n-1，最后得到的一定是0，那么位与的次数就是1的个数

题解：

/** * @param {number} n - a positive integer * @return {number} */
var hammingWeight = function(n) { 
        
    let count = 0
    while(n) { 
        
        n &= n-1
        count++
    }
    return count
};

4.【交换变量】

编写一个函数，不使用临时变量，交换两个变量

题目分析：任何数异或它本身等于0，异或0等于它本身

题解：

var swapNumbers = function(arr) { 
        
    arr[0] = arr[0] ^ arr[1]
    arr[1] = arr[0] ^ arr[1]
    arr[0] = arr[0] ^ arr[1]
    return arr
};

5.【只出现一次的数字】

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？——【力扣136】

题目分析：异或的性质，a ^ a = 0; a ^ 0 = a; 满足交换律和结合律： a ^ b = b ^ a; (a ^ b) ^ c = a ^ (b ^ c);

题解：

/** * @param {number[]} nums * @return {number} */
var singleNumber = function(nums) { 
        
    return nums.reduce((res, item) => res^item)
    // let res = 0
    // for (i = 0; i < nums.length; i++) { 
        
    // res ^= nums[i]
    // }
    // return res
};

6.【汉明距离】

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。——【力扣461】

题目分析：不同位异或为1，则此题转化为求两数字异或后1出现的次数

题解：

/** * @param {number} x * @param {number} y * @return {number} */
var hammingDistance = function(x, y) { 
        
    let z = x ^ y
    let count = 0
    while (z) { 
        
        z &= (z - 1)
        count++
    }
    return count
};

7.【交替位二进制数】

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。——【力扣693】

题目分析：01交替出现，01 & 11 = 01； 11&11=11； 00&11 = 00；所以只要将相邻两位不断位与11——即十进制数字3，结果出现3或者0则表示不是交替位二进制数，否则是。

题解：

/** * @param {number} n * @return {boolean} */
var hasAlternatingBits = function(n) { 
        
    while (n) { 
        
        if ((n & 3) === 0 || (n & 3) === 3) { 
        
            return false
        }
        n >>= 1
    }
    return true
}

8.【两整数之和】

给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。——【力扣371】

题目分析：异或操作符：两个位不相同时为1，否则为0.这个操作符也可以理解为不带进位的加法。位与操作符，都为1时才为1，否则为0，因此&可以理解为只含进位加法。a + b = (a ^ b) + ((a & b) << 1)；a ^ b是无进位的相加； a&b得到每一位的进位；让无进位相加的结果与进位不断的异或， 直到进位为0； 题解：

/** * @param {number} a * @param {number} b * @return {number} */
var getSum = function(a, b) { 
        
    while (b != 0) { 
        
        const carry = (a & b) << 1
        a = a ^ b
        b = carry
    }
    return a
	// return b === 0 ? a : getSum(a ^ b, (a&b)<<1)
}