二进制位运算的魔力

发表于 分类于 阅读次数： 本文字数： 478
二进制位运算的魔力

本文仅用来收集一些二进制位运算的小技巧

简介

关于原码、反码、补码

  • 原码：符号位+数值位
  • 反码：符号位不变，数值位取反
  • 补码：反码+1

关于数的存储方式

  • 正数的存储为：原码
  • 负数的存储为：补码

a & -a

  • a & -a 的结果是 a 的二进制表示中最低位的 1 所在位的值
1
2
3
4
5
6
56 & -56

56   0011 1000
-56  1100 1000
----------------
8    0000 1000

a & (2^n - 1)

当对一个数 a 求模 2^n 时，可以使用 a & (2^n - 1) 来代替 a % 2^n，其中 n 为正整数

1
2
3
4
5
6
100 mod 16

100  0110 0100
15   0000 1111
----------------
4    0000 0100

bitmap

bitmap 是一种数据结构，用来表示一个很大的整数集合，每个整数的出现与否用一个二进制位来表示，这种数据结构可以非常节省内存空间

例如：记录当日登录用户数，假设总共用户数为 1000 万，那么需要 1000 万个二进制位，即 1250000 字节，约 1.2M，最后统计时，只需要遍历一遍二进制位，将二进制位为 1 的个数加起来即可得到当日登录用户数