位运算总结

位运算

• 一、位运算基本概念
  • 1. 汉明重量
  • 2. 汉明距离
  • 3. Brian Kernighan 算法
  • 4. lowbit操作

一、位运算基本概念

1. 汉明重量

  汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是1的个数。

2. 汉明距离

  汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以d（x,y）表示两个字x,y之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。

3. Brian Kernighan 算法

  用于去掉二进制数字的最后面的一位1，也常用于计算汉明权重。   算法：x & (x - 1)。   例题：LeetCode201、LeetCode461

4. lowbit操作

  用于保留原二进制数字的最后一位1对应的数字，常用于树状数组。   算法：x & (-x)。

更多算法小技巧分享，请关注小博的博客"划水大圣"~