当前位置:网站首页>位级运算之提取位级表示的最高位
位级运算之提取位级表示的最高位
2022-08-03 13:34:00 【Once_day】
位级运算之提取位级表示的最高位
Author:Once day Date:2022年7月31日
漫漫长路刚刚开始,不要甘于平凡。
本算法基于C语言环境。
1.引言
可以只依靠基本的位级运算来提取位级表示的最高位。
如值0xFF00,返回0x8000,值0x6600,返回0x4000。
简单的处理是从最高位向右依次判断,不过存在一种无需判断,且复杂度为对数级别的方法。
2.实现
假设一共32位,即0x00707000,看成32位的向量 b 31 b n 30 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ b 1 b 0 b_{31}bn_{30}······b_1b_0 b31bn30⋅⋅⋅⋅⋅⋅b1b0。
那么可以将其分成两部分,利用折半查找的思想,即 u 1 = b 31 b 30 ⋅ ⋅ ⋅ b 17 b 16 u_1=b_{31}b_{30}···b_{17}b_{16} u1=b31b30⋅⋅⋅b17b16和 u 2 = b 15 b 14 ⋅ ⋅ ⋅ b 1 b 0 u_2=b_{15}b_{14}···b_{1}b_{0} u2=b15b14⋅⋅⋅b1b0。
直接进行与运算,判断u1和u2里是否含有1:
unsigned x=0x00707000;
x=(x&0xffff0000)||(x&0x0000ffff);
根据与运算符的规则,如果最高位1在 u 1 u_1 u1, 那么x的值为x&0xffff0000
,所有 u 2 u_2 u2部分值都会被抹去。反之,x的值为x&0x0000ffff
,所有 u 1 u_1 u1部分值都会被抹去。
因此其值变为0x00700000。此时再折半判断:
- 若u1包含最高位1,则在 u 11 = b 31 b 30 ⋅ ⋅ ⋅ b 25 b 24 u_{11}=b_{31}b_{30}···b_{25}b_{24} u11=b31b30⋅⋅⋅b25b24和 u 12 = b 23 b 22 ⋅ ⋅ ⋅ b 17 b 16 u_{12}=b_{23}b_{22}···b_{17}b_{16} u12=b23b22⋅⋅⋅b17b16里判断。
- 若u2包含最高位1,则在 u 21 = b 15 b 14 ⋅ ⋅ ⋅ b 9 b 8 u_{21}=b_{15}b_{14}···b_{9}b_{8} u21=b15b14⋅⋅⋅b9b8和 u 12 = b 7 b 6 ⋅ ⋅ ⋅ b 1 b 0 u_{12}=b_{7}b_{6}···b_{1}b_{0} u12=b7b6⋅⋅⋅b1b0里判断。
这两种情况实际上使互斥的,即 u 11 u_{11} u11和 u 12 u_{12} u12会同时有可能,但 u 11 u_{11} u11和 u 21 u_{21} u21不可能同时发生。
因此合并成两种判断情况:
- 最高位在 u 11 u_{11} u11或 u 21 u_{21} u21,此时
x&(0xff00ff00)
。 - 最高位在 u 12 u_{12} u12或 u 22 u_{22} u22,此时
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);
其复杂度为 l o g 2 w log_2w log2w,w为位级表示的位数。
完…
边栏推荐
- [OpenCV] Book view correction + advertising screen switching Perspective transformation image processing
- ideaIU-2020.1下载
- An animation optimization of shape tween and optimization of traditional tweening
- Basic principle of the bulk of the animation and shape the An animation tip point
- 有哪些好用的IT资产管理平台?
- HCIP-第十二天-MPLS+VNP
- Nanoprobes金脂质偶联物的相关应用
- 驻冰岛使馆提醒旅冰中国公民务必加强安全防护
- VLAN experiment
- Golang 字典 map
猜你喜欢
[web penetration] detailed explanation of CSRF vulnerability
[OpenCV] Cascade classifier training model
Basic principle of the bulk of the animation and shape the An animation tip point
使用Typora+EasyBlogImageForTypora写博客,无图床快速上传图片
如何合理安排一天,做到高效备考?
HCIP 第十六天笔记(SVI、生成树协议)
[Blue Bridge Cup Trial Question 48] Scratch Dance Machine Game Children's Programming Scratch Blue Bridge Cup Trial Question Explanation
Zhang Le: The Golden Triangle of R&D Efficiency and Practice in the Field of Demand and Agile Collaboration|Live Review
升级农企业务运营建设,智慧供应链管理平台打造“共赢生态链”
HCIP-第十二天-MPLS+VNP
随机推荐
Golang 字典 map
Nanoprobes 金纳米颗粒标记试剂丨1.4 nm Nanogold 标记试剂
标题 node第一个服务器程序
PyTorch框架训练线性回归模型(CPU与GPU环境)
使用百度EasyDL实现施工人员安全装备检测
HCIP-第十二天-MPLS+VNP
Golang structs & methods
短视频的头号玩家:抖音产品体验报告
参数量仅0.5B,谷歌代码补全新方法将内部生产效率提升6%
优思学院|2022年获美质协ASQ和ILSSI奖项的《精益六西格玛的十条戒律》
【OpenCV】 级联分类器训练模型
[OpenCV] Cascade classifier training model
使用Typora+EasyBlogImageForTypora写博客,无图床快速上传图片
函数柯里化
将移位距离和假设外推到非二值化问题
JS get browser type
数据科学家 Agnis Liukis :在ML领域,初学者踩过的5个坑
“芯片法案”通过后,美光承诺在美国扩产
d write binary
Golang 数组和切片