位运算的应用 - 与 / AND / &

创建时间:
2014-06-14 11:24
最近更新:
2018-07-17 23:20

AND 运算通常用于二进制取位操作,例如一个数 AND 1 的结果就是取二进制的最末位、AND (1<<n) 的结果就是取 2 进制的第 n 位。

限制最大值 (上限),相当于取模运算

以下代码 限制 x 不大于 31。Twitter Snowflake 的 毫秒内序号 自增时 采用了本算法。
x & 0x1f

判断整数奇偶

假设有一个整数 a,a & 1 这个表达式可以用来判断 a 的奇偶性。
二进制的末位为 0 表示偶数,最末位为 1 表示奇数。
使用 a % 2 来判断奇偶性和 a & 1 是一样的作用,但是 a & 1 更快。

可用代码 (JavaScript)

function IsEvenOrOdd (number) {
	return (number & 1) === 0;
}

可用代码 (C#)

public bool IsEvenOrOdd (int i) {
	return (i & 1) == 0;
}

判断一个整数是否是处于 0-65535 之间 (常用的越界判断)

(a >= 0) && (a <= 65535) 可能要两次判断。
a & ~((1 << 16) -1) 位运算 只要一次,后面的常数是编译时就算好了的,其实只要算一次 逻辑与 就行了。

可用代码 (JavaScript)

function IsBetween0_65535 (number) {
	return (a & ~((1 << 16) -1)) ===0;
}

判断 n 是否是 2 的正整数冪

(!(n & (n-1))) && n

Example

如果 n = 16 = 10000,n-1 = 1111
那么 10000 & 1111 结果为 0。

Example

如果 n = 256 = 100000000,n-1 = 11111111
那么:100000000 & 11111111 结果为 0。
因为:如果一个数 a 他是 2 的正整数幂,那么 a 的二进制形式必定为 1000... (后面有 0 个或者多个 0),那么结论就很显然了。

可用代码 (JavaScript)

function IsPowerOfTow (number) {
	return (number > -1) && (number & (number -1) == 0);
}

C# 中的 public class System.FlagsAttribute 指示可以将枚举作为 位域 (即一组标志) 处理。也是利用了位运算。
例如:在 GridView 的 RowDataBound 事件中,判断是否是 EditItemTemplate 里的控件最好用:
if((e.Row.RowState & DataControlRowState.Edit) != 0)
而不是:
if(e.Row.RowState == DataControlRowState.Edit)

统计一个整数的二进制表示中 1 的个数

可用代码 (JavaScript)

function CountDigit1 (number) {
	var i = 0;
	while(number !== 0) {
		number &= number - 1;
		i++;
	}
}