当前位置：首页 > article >正文

求二进制最低位1和最高位1的方法，以及反转二进制，复杂度O(1)

article 2024/9/20 14:27:36

本文主要对三个二进制操作算法进行介绍，它们都是O(1)的。相对于暴力移位去计算，效率会高很多。这三个算法分别是获取最低的1的比特位、获取最高1的比特位，反转二进制。

(1) 获取最小的1位

法1

int lowbit(int x){
	return x & -x;  // 自已思考下哈，很容易理解
}

举个例子，例如x=1256, 则：

 x:    00000000000000000000010011101000
-x:    11111111111111111111101100011000
x&-x   00000000000000000000000000001000

法2

int lowbit(int x){
	return (x & (x-1)) ^ x;
}

(2) 获取最高的1位

法1

int higbit(int x){
	return reverse(lowbits(reverse(x)));
}

reverse() 函数的作用反转二进制位，复杂度也是O(1), 在后面介绍

法2

引用这篇文章的方法：https://blog.csdn.net/qq_41709801/article/details/88371152
原理是把最高位的1扩散到之后的每一位

unsigned hight_bit(unsigned x){//0010 1100 0000 0000 0000 0000 0000 0000 0000 0001
	x= x|(x>>1);              //0011 1110 0000 0000 0000 0000 0000 0000 0000 0000
	x= x|(x>>2);              //0011 1111 1000 0000 0000 0000 0000 0000 0000 0000
	x= x|(x>>4);              //0011 1111 1111 1000 0000 0000 0000 0000 0000 0000
	x= x|(x>>8);              //0011 1111 1111 1111 1111 1000 0000 0000 0000 0000
	x= x|(x>>16);             //0011 1111 1111 1111 1111 1111 1111 1111 1111 1111
	x= x|(x>>32);
	// 如果数特别大， 这里感觉会溢出， 所以这里只使用于小于数据最大值1/2的数。
	return (x+1) >> 1;        //0100 0000 0000 0000 0000 0000 0000 0000 0000 0000
}

反转二进制数

使用递归的方式

int reverse(int x){
	x = ((x >> 1)  & 0x55555555) | ((x & 0x55555555) << 1);
	x = ((x >> 2)  & 0x33333333) | ((x & 0x33333333) << 2);
	x = ((x >> 4)  & 0x0f0f0f0f) | ((x & 0x0f0f0f0f) << 4);
	x = ((x >> 8)  & 0x00ff00ff) | ((x & 0x00ff00ff) << 8);
	x = ((x >> 16) & 0x0000ffff) | ((x & 0x0000ffff) << 16);
	return x;
}