把一个无符号整数的比特位反转顺序。
有很多种方法来实现这个。我们这里给出一个算法:通过异或运算来交换,然后用分治方法来优化它。
提示:
你怎么把第i个和第j个位置的bit给交换了呢?如果你能用异或来实现,试着给出算法。
异或交换的小技巧:
如果一共有n个bit,反转它可以通过最少n/2次交换,最多n次交换来完成。技巧就在于实现一个交换函数swapBits(i,j),用来交换位置在i和j的两个bit。你应该还记得异或运算:0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, 和 1 ^ 0 == 1。
我们只要在第i位和第j位的bit不同时交换就行了。我们用异或来检测这两位bit是否相同。然后我们还需要切换这两个位置的bit值,我们可以再次用异或来完成操作。通过异或,两个位置的值都可以被切换了。
typedef unsigned int uint; uint swapBits(uint x, uint i, uint j) { uint lo = ((x >> i) & 1); uint hi = ((x >> j) & 1); if (lo ^ hi) { x ^= ((1U << i) | (1U << j)); } return x; } uint reverseXor(uint x) { uint n = sizeof(x) * 8; for (uint i = 0; i < n/2; i++) { x = swapBits(x, i, n-i-1); } return x; }
(译者注:上面的其中一行代码:x ^= ((1U < < i) | (1U << j));是为了切换两个位置的bit值,可以看个例子:x = 1001,--> x ^= ((1U < < 1) | (1U << 3)) --> x = 1001 ^ (1010) –> x = 0011 )
用这种异或方法来反转bit位的时间复杂度是O(n),n是传入的无符号整数的比特位数。
分而治之:
记得归并排序是怎么做的吧?让我们看一下当n=8(一字节)时是怎么样的:
01101001 / \ 0110 1001 / \ / \ 01 10 10 01 /\ /\ /\ /\ 0 1 1 0 1 0 0 1
第一步是交换所有奇数和偶数位置的bit。然后交换连续成对的bit,依此类推……
因此,一共只要log(n)次操作就能完成。
下面的代码展示了一个特定的当n==32时的例子——当然,它也能很简单的去适配当n更大时的情况。
uint reverseMask(uint x) { assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits). x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16); return x; }
小记:
这不是反转bit位的唯一方法,也不是效率最高的。你想要探索更多关于反转bit位的算法/灵感,请访问这里:Bit Twiddling Hacks(译者注:该链接里真的很多好东东)。
英文原文在这里,由www.newhottopic.com翻译。
相关推荐
BiFeO3磁矩反转文章,3M文章详细计算了BFO磁矩反转机制。
克服腔QED中比特反转错误的无退相干子空间量子计算,陈月月,冯勋立,本文提出了一种抑制集体比特反转型错误的无退相干子空间(DFS)量子计算方案。该方案利用囚禁在腔中的原子基态来编码量子信息,且
基于Qt的整数按位反转实现,主要是利用了Qt数字转字符串,字符串转数字的工能。
很准的指标,有压力位。反转信号.用了长时间。大家共用
matlab开发-时间反转和频谱反转信号。用户指定语音信号的时间反转和/或频谱反转。
C++ 单链表反转 C++ 单链表反转 C++ 单链表反转
ldpc码的比特反转译码算法利用C语言实现,虽然简单但比较完整
labview 16进制反转字符串
对ldpc进行比特翻转译码,里面有详细的备注介绍,程序里的G矩阵和H矩阵需要自己给定
给定一个整数,请将该数各个位上的数反转得到一个新数。新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零。 Input 输入有多组数据,每组数据就一行为一个整数N(-...
时间反转镜算法进行定位估计,利用声场波导特性,实现信号的增强和减弱
深入理解密码学中CBC模式模式下的加解密过程及其存在的问题。并用一道CTF经典例题深入讲解字节反转攻击。
济阳坳陷负反转构造反转强度分析,李伟,吴智平,反转强度分析是反转构造研究的重要内容。反转强度定量分析的方法有反转率、位移-距离曲线等,但上述方法均不能适用于完全反转的
控制反转 依赖注入的c#实现,很好的教程。
实现图片的反转,就像连连看一下。
一个对时间反转镜技术的原理的简单的描述和仿真。
将一段字符串反转如“abcdef”反转后“fedcba”
量化交易策略之动量与反转交易python版,用户可修改参数进行自定义,可借助米匡、聚宽等网站平台实现量化交易。动量反转策略被证实为长久以来仍有明显效果的交易策略。
资源名:时间反转镜_matlab.zip 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定经验的开发...
RTOS优先级反转问题分析