5

Bit Arithmetic | 一直进步 做喜欢的

 1 year ago
source link: https://xfliu1998.github.io/2023/03/27/Bit-Arithmetic/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

一直进步 做喜欢的

Bit Arithmetic

Created2023-03-27|Updated2023-03-27|Data Structures and Algorithms
Word count:831|Reading time:2min|Post View:1|Comments:
  • 简介：程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。常见的运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>是带符号右移 >>>无符号右移动)。
  • 优点：可以直接对二进制数进行操作，执行速度比较快，而且可以节省内存空间，特别是在处理大规模数据时，优势更加明显。
  • 应用场景：常用于处理二进制数据，如位图压缩、哈希表实现、位集合操作等。也可以用于加密算法、图像处理、网络协议等领域。
  • 时间复杂度：通常是O(1)，因为它们直接对二进制位进行操作，而不需要循环或递归等复杂的计算过程。
  • 技巧：
    1. 按位与&：
      • 判断一个数的奇偶性（x & 1 == 0表示x是偶数，x & 1 == 1表示x是奇数）
      • 清零一个数的某一位(x &= ~(1 << n)表示将x的第n位清零)
      • 判断一个数是否是2的幂次方。例如：(x & (x - 1)) == 0 表示x是2的幂次方
      • Brian Kernighan算法：消除数字n的二进制表示中的最后一位1，也即计算汉明权重（Hamming Weight）：n & (n-1)
      • 取出 x 的二进制表示中最低位的1 ：x & -x
    2. 按位或|：
      • 将一个数的某一位设置为1 ( x |= (1 << n) 表示将x的第n位设置为1)
    3. 按位异或^：
      • 可以用来交换两个变量的值（a ^= b; b ^= a; a ^= b;）
      • 检查一个数是否出现了奇数次。对于数组中出现两次的数，使用异或操作可以找到它们，任何数和其自身做异或运算，结果是0，即 a ^ a = 0
      • 任何数和 0 做异或运算，结果仍然是原来的数，即 a ^ 0 = a
      • 异或运算满足交换律和结合律，即a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a) = b ⊕ 0 = b
    4. 左移位<<：可以用来计算2的幂次方（1 << n表示2的n次方）
    5. 右移位>>：可以用来计算除以2的幂次方（x >> n表示将x除以2的n次方）
  • 常用方法：
    • bin()获取数字的二进制值
    • ord()输入单个字符返回其ASCII值（0-255）或unicode值
    • chr()输入一个整数[0，255]返回其ASCII值
    • int("s",x)将指定进制x的字符s转换成十进制值
    • 正数的反码和补码都与原码相同。负数的二进制用补码表示。负数的反码为对该数的原码除符号位外各位取反。负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加1 。

参考博客：

位运算
题目 技巧 难度
✅67. 二进制求和 简直不是人想出来的！！！ 🌟
✅136. 只出现一次的数字 a ^ 0 = a; a ^ a = 0 🌟
✅137. 只出现一次的数字 II (a >> i) & 1 取出a的第i位 🌟🌟
✅187. 重复的DNA序列 用二进制表示x = ((x << 2) | bin[ch]) & ((1 << 20) - 1) 🌟🌟
❌✅190. 颠倒二进制位 还有个分治法 🌟
✅191. 位1的个数 n & (n - 1)消除二进制n的最后一位1 🌟
✅201. 数字范围按位与 寻找公共前缀，n&(n-1)消除最后一位1 🌟🌟
✅231. 2 的幂 同191 260 🌟
✅260. 只出现一次的数字 III x的最后一位1：x & -x 🌟🌟
✅268. 丢失的数字 a ^ a = 0 🌟
❌287. 寻找重复数 难以理解 🌟🌟
✅318. 最大单词长度乘积 将字母用掩码表示，取并为0则表示二者没用重复字符 🌟🌟
❌✅338. 比特位计数 x&(x-1)消除1，还有动态规划解法 🌟
✅342. 4的幂 4的幂是2的偶数次幂，且%3=1 🌟
✅371. 两整数之和 python整型无限长，用32位补码表示32位有符号整型，负数最高位全为1 🌟🌟
✅389. 找不同 ord(a), chr(1) 🌟

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK