位级运算之提取位级表示的最高位

位级运算之提取位级表示的最高位

Author：Once day Date：2022年7月31日

漫漫长路刚刚开始，不要甘于平凡。

本算法基于C语言环境。

1.引言

可以只依靠基本的位级运算来提取位级表示的最高位。

如值0xFF00，返回0x8000，值0x6600，返回0x4000。

简单的处理是从最高位向右依次判断，不过存在一种无需判断，且复杂度为对数级别的方法。

2.实现

假设一共32位，即0x00707000，看成32位的向量 $b_{31}b{n}_{30}\cdot \cdot \cdot \cdot \cdot \cdot b_1{b}_0$。

那么可以将其分成两部分，利用折半查找的思想，即$u_1=b_{31}{b}_{30}\cdot \cdot \cdot b_{17}{b}_{16}$和$u_2=b_{15}{b}_{14}\cdot \cdot \cdot b_1{b}_0$。

直接进行与运算，判断u1和u2里是否含有1：

unsigned x=0x00707000;
x=(x&0xffff0000)||(x&0x0000ffff);
1
2

根据与运算符的规则，如果最高位1在$u_1$， 那么x的值为x&0xffff0000，所有$u_2$部分值都会被抹去。反之，x的值为x&0x0000ffff，所有$u_1$部分值都会被抹去。

因此其值变为0x00700000。此时再折半判断：

• 若u1包含最高位1，则在$u_{11}=b_{31}{b}_{30}\cdot \cdot \cdot b_{25}{b}_{24}$和$u_{12}=b_{23}{b}_{22}\cdot \cdot \cdot b_{17}{b}_{16}$里判断。
• 若u2包含最高位1，则在$u_{21}=b_{15}{b}_{14}\cdot \cdot \cdot b_9{b}_8$和$u_{12}=b_7{b}_6\cdot \cdot \cdot b_1{b}_0$里判断。

这两种情况实际上使互斥的，即$u_{11}$和$u_{12}$会同时有可能，但$u_{11}$和$u_{21}$不可能同时发生。

因此合并成两种判断情况：

• 最高位在$u_{11}$或$u_{21}$，此时x&(0xff00ff00)。
• 最高位在$u_{12}$或$u_{22}$，此时x&(0x00ff00ff)。

以此类推，则可表示为：

unsigned x=0x00707000;
x=(x&0xffff0000)||(x&0x0000ffff);
x=(x&0xff00ff00)||(x&0x00ff00ff);
x=(x&0xf0f0f0f0)||(x&0x0f0f0f0f);
x=(x&0xbbbbbbbb)||(x&0x33333333);
x=(x&0xaaaaaaaa)||(x&0x55555555);
1
2
3
4
5
6

其复杂度为$lo{g}_{2}w$，w为位级表示的位数。

---

---

完…