摘要：相信大家都知道二进制数按位运算的规则来看一些简单的例子单纯的二进制位之间的这些运算相当简单，但对我们实际编程并没有直接帮助，因为编程过程中需要的经常是数字间的运算，比如。
先来看LeetCode上的Divide Two Integers题目要求：
Divide two integers without using multiplication, division and mod operator.
就是说不用乘法，除法，求模运算来实现两个整数相除，看起来很简单，我可以用除数减去被除数，直到除数小于被除数，记录减法操作的次数即可。假设是计算m/n，那么时间复杂度为O(m/n)。用Python实现后，Time Limit Exceeded。我们考虑有没有更加优化的算法呢？
如果很难想得到，那就先来回忆下二进制数按位运算的一些知识。
二进制数按位运算计算机里面所有数据都存储为0，1串，所有的运算归根到底都转为二进制数的运算。相信大家都知道二进制数按位运算的规则：
来看一些简单的例子：
1010 & 1100 = 1000 1010 | 1100 = 1110 1010 ^ 1100 = 0110 1010 << 2 = 101000 1010 >> 2 = 10 ~1010 = 0101
单纯的二进制位之间的这些运算相当简单，但对我们实际编程并没有直接帮助，因为编程过程中需要的经常是数字间的运算，比如 5*(2^4) 。真的是这样吗？接着往下看！
计算机中数字的存储方式我们都知道计算机中万物皆为0、1，将万物变为0、1的过程叫做编码，这里我们只讨论将数字编码为0、1的过程。
计算机中对数字的表示有三种方式：原码，反码，补码：
原码表示法在数值前面增加了一位符号位（即最高位为符号位）：正数该位为0，负数该位为1。比如十进制3如果用8个二进制位来表示就是 00000011， -3就是 10000011。
反码表示方法：正数的反码是其本身；负数的反码是在其原码的基础上，符号位不变，其余各个位取反。
补码表示方法：正数的补码是其本身；负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1。 (即在反码的基础上+1)
原码容易被人脑直接识别并用于计算，但是对于计算机来说并不友好。所以在计算机系统中，数值一律用补码来表示、运算和存储。使用补码，可以将符号位和数值域统一处理，将加法和减法统一处理。此外，补码与原码相互转换，其运算过程是相同的，不需要额外的硬件电路。详细的解释可以参考原码, 反码, 补码详解。
数字的按位运算计算机中数字存储为补码形式，各个数之间的运算也是对它们的补码做运算，而且得到的结果也是补码，如下图：
各种编程语言都提供了对补码的二进制位直接进行运算的方法。以Python为例：
>>> 0b1010 & 0b1100 8 #1000 >>> 0b1010 | 0b1100 14 #1110 >>> 0b1010 ^ 0b1100 6 #0110 >>> 0b1010 << 2 40 #101000 >>> 0b1010 >> 2 2 #10 >>> ~0b1010 -11 #10000000 00000000 00000000 00001011 >>> type(0b1010)
上面0b开头的0、1串表示整型数字，在32位操作系统中，Python中int类型一般占32个二进制位，以最后一个求反运算为例子，1010的补码为
00000000 00000000 00000000 00001010
求反操作后为：
11111111 11111111 11111111 11110101
即为-11(原码为：10000000 00000000 00000000 00001011)的补码。（对一个数的补码求补码即可得到该数的原码）
另辟蹊径的按位运算那么按位运算在实际编程中可以扮演哪些角色呢？简单点地，可以用来判断奇、偶数：num & 0x1，或者对一个数变换符号：~num + 1；复杂点的可以用来交换两个数，求绝对值等等。
> 不用额外的变量实现两个数字互换。
def swap(num_1, num_2):
num_1 ^= num_2
num_2 ^= num_1
num_1 ^= num_2
return num_1, num_2
证明很简单，我们只需要明白异或运算满足下面规律：
0^a = a;
a^a = 0;
a^b^c = a^c^b;
巧妙运用异或可以高效解决很多问题，比如 找出数组中只出现了一次的数（除了一个数只出现一次外，其他数都是出现两次），以及它的升级版：数组中只出现1次的两个数字(百度面试题)。
> 不用判断语句来实现求绝对值。
def bit_abs(num):
negative = num >> 31
return (num ^ negative) - negative
这里假设程序运行环境中操作系统为32位，int型整数(不考虑整数溢出)用32位存储，因此可以用 num>>31 取出符号位，后面的部分留给大伙证明。
Leetcode 题目思路回到文章开始提到的题目中，我们对除数减去被除数的过程稍作改进。假设求m/n，我们不一次次的 m-n，而是找到n的一个倍数，使得m-x*n尽可能小，这样能减少循环减法的次数，进而提高效率。我们知道在按位操作中，n << k相当于 n * 2^k，因此可以用2^k 来找合适的x。
我们需要这样的一个数字k，它使得n 2^k < m < n 2^(k+1)， 然后用m - n*2^k，得到新的m"。再找相应的k"，做减法，如此循环即可。代码放在这里。
原文地址
相关阅读
Pyhon wiki: BitwiseOperators
位操作基础篇之位操作全面总结
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/37621.html
摘要：检查设定位操作符还有一些其他有用的位屏蔽应用。请注意，位掩码中的位将有效地关闭十进制数中的相应位，因为。 原文标题：Interesting use cases for JavaScript bitwise operators原文地址：https://blog.logrocket.com/in... 本文首发于公众号：符合预期的CoyPan JavaScript提供了几种运算符，可以对...
摘要：位运算符位运算符与逻辑运算符类似，但是位运算符是对每一位进行计算。上面说到的按位取反加，就可以写成移位运算符右移与无符号右移相似，是将整数所有的位向右移动位，抛弃个低位。空出来的低位用的最高位值补全。 定点数据再计算机中的表示方法 例如一个整数类型（int)的数据在内存中占用了32位。通俗的讲就是在内存中挖了32个坑，每一个坑里可以放一个0或者1. 00000000 11111111 ...
摘要：例如，十进制数，用二进制表示则为。按位操作符操作数字的二进制形式，但是返回值依然是标准的数值。不同为真相同为假二进制按位异或运算从左到右按位非为真，为假对每一项进行非操作，遇真则假，遇假则真。 二进制与十六进制 二进制用 0 1 表示 2= 10十六进制 前缀0x 用0123456789ABCDEF表示 2= 0x2二进制与十六进制的转换十六进制的每位 等于二进制的四位 十六进制 0x...
摘要：例如注意字符串中的负十六进制数字是一个特殊情况，如果你用解析，结果是不正确的。转换十六进制数时要小心，如果你不知道要转换对象的类型，不要使用。字符串转换为数字的方式总结负十六进制数字符串转换为数字时。 摘要 ：JavaScript 是一个神奇的语言，字符串转数字有 5 种方法，各有各的坑法! 原文: Converting Strings to Number in Javascript...
阅读 2471·2021-10-08 10:04
阅读 2710·2021-09-06 15:02
阅读 728·2019-08-30 13:50
阅读 1517·2019-08-30 13:21
阅读 2567·2019-08-30 11:15
阅读 2088·2019-08-29 17:19
阅读 1551·2019-08-26 13:55
阅读 1246·2019-08-26 10:15
