位运算

对于位运算位运算就是二进制运算，咱们晓得计算机cpu运算最底层的物理实现，就是高低电平输出，形象成数学符号就是二进制01输出。因而位运算对cpu来说是最高效的，因为咱们用它的“母语”和它交换。因而，juc库很多中央都有位运算的影子，就是为了提高效率，有的中央用得奇妙真是让人惊叹，让人大呼还能这样，既优雅又简洁，应了中国的那句老话，大道至简！ 使用示例给定一个整型容量initialCapacity，计算这个容量最近的2的n的数 initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++;上述代码翻译成人类语言就是，给定一个数，咱们从二进制的角度看这个数;比方8，它的二进制是1000；把它最高位1之后的其余位都变成1，而后加1;即1000 -> 1111,加1后变成10000，对应的十进制是16. 下面这段代码其实是摘自ArrayDeque的 allocateElements，其实它还思考了溢出变成正数状况，就是二进制最高位是1的状况。 相似的还有jdk1.8 hash map的容量初始化修改计算，为啥cap要先减去1，为了使得输出刚好是2的n次方的数的容量不须要再修改，比方8，对应的二进制是1000，减去1后的二进制是0111，对应的十进制是7，用同样的算法，算出后果是8，和输出的8统一。

家喻户晓，lowbit是为了获取一个数的二进制中最低位的1对应的值，比方lowbit(10) = 10，因为10的二进制表白是1010。 lowbit的实现lowbit有两种实现形式： x & (x ^ (x - 1))以二进制数x = 11110000为例，x - 1=11101111，容易发现，其实就是将x的最初一个1变为0，再将前面的0都变成1，这样以来，再与x做异或： 11110000 ^ 11101111后果是00011111。也就是把原数x最初一个1以及前面的 0都变成1，把最初一个1后面的1都变成0。既然后面都是零了，那么只有和原数x做和的操作，即可将异或的后果最初一个1前面的1都变成0，也就是 11110000 & 00011111失去00010000，这样就优雅得失去了最初一个1示意的数，也就是原数x的最大的能够整除的数。这里x的十进制是240，lowbit的后果是16=2^4。x & -x这种算法其实是利用了计算机的补码性质。计算机为了示意正数，将对应的负数二进制全副取反再加一。以x=11010000为例，-x=00101111 + 1 = 00110000，能够看到，取反加一后原数最初一个1前面的所有0还是0（因为加法的进位操作），原数最初一个1前的所有1都变成了0，而所有0都变成了1，其实次要外围就是将最初一个1后面的数都翻转，这样再与原数进行或操作，最初一个1后面都会是0，也就是 11010000 & 00110000后果是00010000。lowbit的利用统计二进制下1的个数先用原数计算出lowbit(x)，而后用原数减去这个数，再一直lowbit。int ans = 0;while(x > 0){ x -= x & -x; ans++;}这也是树状数组的实现原理。基于这个操作咱们能够将合成出一个整数能够由哪些的2的幂相加形成。比方11110000也就是240=2^4+2^5+2^6+2^7。 参考： https://www.jianshu.com/p/6c3...https://blog.csdn.net/qq_4172...https://www.cnblogs.com/fusiw...

class Solution { public int add(int a, int b) { while(b!=0) { int c = (a & b)<<1; int n = a ^ b; a = n; b = c; } return a; }}

异或满足交换律，第一步异或，雷同的数其实都对消了，剩下两个不同的数。这两个数异或后果必定有某一位为1，不然都是0的话就是雷同数。找到这个位，不同的两个数一个在此位为0，另一个为1。按此位将所有数分成两组，离开后各自异或，雷同的两个数异或必定为0（而且离开的时候，两个数必为一组）。剩下的每组里就是我门要找的数 class Solution { public int[] singleNumbers(int[] nums) { //用于将所有的数异或起来 int k = 0; for(int num: nums) { k ^= num; } //取得k中最低位的1 int mask = 1; //mask = k & (-k) 这种办法也能够失去mask，具体起因百度 哈哈哈哈哈 while((k & mask) == 0) { mask <<= 1; } int a = 0; int b = 0; for(int num: nums) { if((num & mask) == 0) { a ^= num; } else { b ^= num; } } return new int[]{a, b}; }}作者：eddieVim链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jie-di-qi-jiang-jie-fen-zu-wei-yun-suan-by-eddievi/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

观感度：???????????????????? 口味：西南小炒肉 烹饪工夫：10min 本文已收录在前端食堂同名仓库Github github.com/Geekhyt，欢迎光临食堂，如果感觉酒菜还算可口，赏个 Star 对食堂老板来说是莫大的激励。初识位运算记忆& ，与 两个位都为 1 时，后果才为 1| ，或 两个位都为 0 时，后果才为 0^ ，异或 两个位雷同为 0 ，相异为 1～，按位取反 所有 0 变 1，1 变 0<<，左移 各二进位全副左移若干位，高位抛弃，低位补 0>>，右移 各二进位全副右移若干位，对无符号数，高位补 0 ，有符号数，各编译器解决办法不一样，有的补符号位，有的补 0了解其实很简略，小学数学题难度，花几分钟看完如果看懂了请点个赞呗。 左移二进制左移一位，就是将数字翻倍。 二进制 110101 向左移一位，就是在开端增加一位 0，也就是 1101010。(此处探讨的是数字没有溢出的状况) 二进制 110101 转化成十进制： 1 2^5 + 1 2^4 + 0 2^3 + 1 2^2 + 0 2^1 + 1 2^0 = 32 + 16 + 0 + 4 + 0 + 1 ...

原题地址：https://leetcode-cn.com/probl... repo 地址: https://github.com/pigpigever...题目剖析????两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。比如说存在这样两个二进制数值： 001100它们之间的汉明距离就是 2，我们要求的就是两个二进制数值中位数不一样的地方，比如你是 1 他是 0，那么汉明距离就 +1。 前置知识????异或运算是相对基础的知识，但是由于在平时的开发中几乎不会用到，难免生疏。这里简单罗列下常见的异或运算： & : 按二进制位进行 与运算，相同位同时为 1 时结果为 1，否则为 0| : 按二进制位进行 或运算，相同位存在 0 和 1 时结果为 1，否则为 1^ : 按二进制位进行 异或运算，相同位相同时为 0，否则为 1>> : 右移运算是将一个二进制位的操作数按指定移动的位数向右移动，移出位被丢弃，左边移出的空位或者一律补 0<< : 左移运算是将一个二进制位的操作数按指定移动的位数向左移位，移出位被丢弃，右边的空位一律补 0梳理逻辑????思路其实很简单，如下： 遍历两个数值，位数不相同那么 +1示例代码????/** * @param {number} x * @param {number} y * @return {number} */var hammingDistance = function(x, y) { let ans = 0 while (x !== 0 || y !== 0) { if ((x & 1) !== (y & 1)) { ans++ } x >>= 1 y >>= 1 } return ans};写在最后一直在 LeetCode 上刷题，之前还加入了组织，有兴趣加入一起学习的同学可以在下方留言或者关注我的微信公众号「tony老师的前端补习班」并在后台留言，可以进群跟大佬们一起学习。 ...

简介众所周知，在计算机中，任何对数的处理都会回归于对相应二进制数的处理。我们把这对应的二进制形式称为机器数（最高位储存符号，“0”是“+”，“1”是“-”），位运算可以对机器数直接进行一元操作（有一个被处理数）或二元操作（有两个）。在平时，位运算比部分正常运算略快；不过当问题本身涉及到对二进制数的转化与处理时，位运算更能发挥巨大的作用。位运算符简介左移运算符 <<对于一个二进制数，我们使用左移操作，它包含被操作值和移位值，左移操作就是将该数每一位上的数向左移动移位值，如0000 0000 0000 0011（3）向左移位1一位成为0000 0000 0000 0110（6）.v<<s上述代码展示了左移运算符的使用，v是被操作的整数值，s是移动位数。对于二进制数，我们知道每一位上等于右边一位的两倍。那么，左移一位即等于乘2。那么3<<1便等价于（1×2^1+1×2^0）×2=6。位移n位，以此类推，等于原值的2^n倍。右移运算符 >>v>>s据左移运算符的功能类推可知，右移运算符即将每一位右移n位。位移后的值等于原值的1/2^n倍。对于位移运算符，位移后腾出的位置用“0”填充，超出边界的值舍弃。按位反运算符 ~位反运算符将每一位转换为它的反面。按位或运算符 |对两个等长二进制整数值操作，若两个数的对应位中只要有一个及以上的“1”，结果新值中此位为“1”，其余情况此位则为“0”。按位异或运算符 ^对两个等长二进制整数值操作，若两个数的对应位中只有一个为“1”，新值相应位为“1”，而若都是“0”或“1”，相应位为“0”。按位与运算符 &对两个等长二进制整数值操作，若两个数的对应位中两个都是“1”，新值相应位为“1”，其余情况新值相应为皆为“0”.

题目输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。分析这是一道考察二进制的题目二进制或运算符（or）：符号为|，表示若两个二进制位都为0，则结果为0，否则为1。二进制与运算符（and）：符号为&，表示若两个二进制位都为1，则结果为1，否则为0。二进制否运算符（not）：符号为~，表示对一个二进制位取反。异或运算符（xor）：符号为^，表示若两个二进制位不相同，则结果为1，否则为0左移运算符m << n 表示把m左移n位，左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0，比如：00001010<<2 = 00101000右移运算符m >> n 表示把m右移n位，右移n位的时候，最右边的n位将被丢弃，同时在最左边补上n个0，比如：00001010>>2 = 00000010我们可以让目标数字和一个数字做与运算这个用户比较的数字必须只有一位是1其他位是0，这样就可以知道目标数字的这一位是否为0。所以用于比较的这个数字初始值为1，比较完后让1左移1位，这样就可以依次比较所有位是否为1。代码function NumberOf1(n){ let flag = 1; let count = 0; while(flag){ if(flag & n){ count++; } flag = flag << 1; } return count;}

题目Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.Example 1:Input: 5Output: TrueExplanation:The binary representation of 5 is: 101Example 2:Input: 7Output: FalseExplanation:The binary representation of 7 is: 111.Example 3:Input: 11Output: FalseExplanation:The binary representation of 11 is: 1011.Example 4:Input: 10Output: TrueExplanation:The binary representation of 10 is: 1010.题目地址讲解这一题的意思是判断一个整数的二进制形式，是否是0和1互相间隔排列的。题目挺简单的，但我想做的是空间O(1)。所以我用两个变量来存储遍历过程中需要保存的前一位和后一位，然后设置一个首次访问flag。遍历一遍二进制，结果就出来了。java代码class Solution { public boolean hasAlternatingBits(int n) { if(n<=2){ return true; } int temp = n; int now = 0; int previous = 0; boolean flag = true; while(temp>0){ if(flag){ now = temp%2; temp >>= 1; flag = false; }else{ previous = now; now = temp%2; if(previous==now){ return false; } temp >>= 1; } } return true; }} ...