[数据结构与算法]LeeCode_位运算

一、位运算概念

位运算主要分为两大类：逻辑位运算和位移位运算

二、 逻辑位运算符

$ 按位与

• 两个相应的二进制位中只要有一个为1，该位的结果值为1，两者都为0才为0

  // 两个相应的二进制位中只要有一个为1，该位的结果值为1
  // 5(base10) = 00000000000000000000000000000101(base2)
  // 3(base10) = 00000000000000000000000000000011(base2)
  let m = 5, n = 3
  let k = m & n
  console.log(k)// 输出：1

|按位或

• 两个相应的二进制位中只要有一个为0，该位值结果为0，否则为1，两者都为1才为1

//两个相应的二进制位中只要有一个为0，该位值结果为0，否则为1，两者都为1才为1
  // 5(base10) = 00000000000000000000000000000101(base2)
  // 3(base10) = 00000000000000000000000000000011(base2)
  let m = 5, n = 3
  let k = m | n
  console.log(k)// 输出：7

^按位异或

• 若参加运算的两个二进制位值相同则为0，不同则为1

  //若参加运算的两个二进制位值相同则为0，不同则为1
  // 5(base10) = 00000000000000000000000000000101(base2)
  // 3(base10) = 00000000000000000000000000000011(base2)
  let m = 5, n = 3
  let k = m ^ n
  console.log(k)// 输出：6

~按位取反

• ~是一元运算符，用来对一个二进制数按位取反，即将0变1，1变0

let bitwiseNot = () => {
  //若参加运算的两个二进制位值相同则为0，不同则为1
  // 5(base10) = 00000000000000000000000000000101(base2)
  // -3(base10) = 11111111111111111111111111111101(base2)
  let m = 5, n = -3
  let j = ~ m
  let k = ~ n
  console.log(j,k)// 输出：-6,2
}

按位取反特殊例子：

~0;  // -1
~-1; // 0
~1;  // -2

三、位移位运算符

>>右移运算符

• 将一个数的二进制右移N位，移到右端的低位被舍弃，高位原来是什么就补什么

  // 5(base10) = 00000000000000000000000000000101(base2)
  // 3(base10) = 00000000000000000000000000000011(base2)
  // -5(base10) = 11111111111111111111111111111011(base2)
  const a = 5;
  const b = 2;
  const c = -5;
  //输出：1(base10)  00000000000000000000000000000001(base2)
  console.log(a >> b);// 5右移两位
  //输出：-2(base10)  11111111111111111111111111111110(base2)
  console.log(c >> b);// -5右移两位

<<左移运算符

• 将一个数的二进制左移N位，右补0

  // 5(base10) = 00000000000000000000000000000101(base2)
  // 3(base10) = 00000000000000000000000000000011(base2)
  const a = 5;
  const b = 2;
  //输出：20(base10)  00000000000000000000000000010100(base2)
  console.log(a << b);// 5左移两位

>>>无符号位移运算符

• 将一个数的二进制右移N位，移到右端的低位被舍弃，对无符号数，高位补0

  // 5(base10) = 00000000000000000000000000000101(base2)
  // 3(base10) = 00000000000000000000000000000011(base2)
  // -5(base10) = 11111111111111111111111111111011(base2)
  const a = 5;
  const b = 2;
  const c = -5;
  //输出：1(base10)  00000000000000000000000000000001(base2)
  console.log(a >>> b);// 5右移两位
  //输出：1073741822(base10)  00111111111111111111111111111110(base2)
  console.log(c >>> b);// -5右移两位

四、例题

136. 只出现一次的数字

来源：力扣

题目描述

题解

var singleNumber = function(nums) {
  let single = 0;
  for(let i=0;i<nums.length;i++){
    console.log(single,nums[i])
    single ^= nums[i]
  }
  return single
};

190. 颠倒二进制位

来源：力扣

题目描述

题解

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function (n) {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    res = (res << 1) + (n & 1);
    n = n >>> 1;
  }

  return res >>> 0;
};

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖