把一个无符号整数的比特位反转顺序。
有很多种方法来实现这个。我们这里给出一个算法:通过异或运算来交换,然后用分治方法来优化它。
提示:
你怎么把第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翻译。
相关推荐
在编程领域,整数的按位反转是一种常见的操作,它涉及到二进制表示下的每一位进行翻转。在给定的“基于Qt的整数按位反转实现”中,我们将探讨如何利用Qt库提供的功能来完成这个任务。Qt是一个强大的跨平台应用程序...
2. 比特反转错误:在量子计算中,比特反转错误是一种常见的量子错误类型,它指的是量子比特的状态从 |0⟩ 变为 |1⟩ 或者相反。这是由于量子系统的退相干引起的,退相干会导致量子信息的丢失和量子系统与环境的耦合...
本项目聚焦于LDPC码的比特反转(Bit Flipping)译码算法,该算法是LDPC码早期且相对简单的译码策略之一。本文将深入探讨LDPC码、比特反转译码算法以及如何用C语言实现这一算法。 首先,LDPC码是由Richard W. ...
### BiFeO3磁矩反转文章 #### 概述与背景 本文主要研究了BiFeO3(铋铁酸铋)中的磁矩反转机制及其与Dzyaloshinskii–Moriya相互作用(DMI)的关系。BiFeO3作为一种典型的多铁性材料,其独特的磁性和电性质使其在信息...
时间反转技术是一种在声学、光学以及无线通信领域广泛应用的高级技术,主要涉及时间反转镜(Time Reversal Mirror, TRM)的概念、原理及其在定位和信号处理中的应用。这个技术的核心是通过精确地复制并逆向播放信号...
时间反转镜(Time Reversal Mirror,TRM)是一种基于物理原理的信号处理技术,它在声学、光学以及通信领域都有广泛的应用。这个技术的核心是利用声波或光波的传播特性,通过逆向传播过程来实现信号的精确聚焦和定位...
位反转电路,也称为比特反置或位倒序,是一种数字逻辑电路,其功能是将输入序列中的每一位按照预设的顺序进行翻转。这种技术常用于数据编码、错误检测与校正,以及在特定的通信协议中,如在电子政务系统中的数据交换...
5. **时间反转播放**:最后,将反转后的信号反向播放,即从后向前播放。这可以通过MATLAB的数组索引操作来实现。 在“reversed_time_1”这个文件中,很可能是包含了实现这些步骤的MATLAB源代码。代码可能包括定义...
很准的指标,有压力位。反转信号.用了长时间。大家共用
循环结束后,`previous`指针会指向原链表的最后一个节点,也就是反转后的新链表的头节点。因此,我们将`pHead`设置为`previous`,使得`pHead`指向反转后的链表头。 在`main`函数中,我们创建了两个节点`node1`和`...
字节反转攻击利用了CBC模式的一个特性,即修改一个密文块可以改变与其相邻明文块的相应位,但不会影响其他明文块的位。假设我们能猜测或部分知道明文块Pn,通过修改前一个密文块Ci-1为Ci-1 XOR Pn XOR A,解密后,Pn...
时间反转技术在多个领域有广泛的应用,例如: - **超声成像**:通过时间反转技术,可以提高超声波图像的分辨率和信噪比,用于医疗诊断。 - **通信**:在无线通信中,时间反转可以改善信号传输的效率和可靠性,特别...
给定一个整数,请将该数各个位上的数反转得到一个新数。新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零。 Input 输入有多组数据,每组数据就一行为一个整数N(-...
java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和反转义工具类 java 转义和反转义工具类java 转义和...
labview 16进制反转字符串
- 当高优先级组的某个消息连续发送失败超过设定阈值时,该消息的动态反转标识位被设置为1,使得该消息的优先级降低,从而允许低优先级消息有机会发送。 - 反转后的消息只有在其成功发送后,动态反转标识位才会恢复为...
逆天反转图通达信指标公式源码分析 本文将对逆天反转图通达信指标公式源码进行详细分析,包括指标公式的解释、代码结构分析、变量定义、指标计算逻辑、画图逻辑等方面的内容。 一、指标公式解释 逆天反转图通达信...
`将反转后的浮点型图像数据转换回8位无符号整型,以便于显示和保存。`uint8`函数负责这个转换。 为了可视化反转前后的效果,MATLAB的`subplot`函数被用来创建一个包含两个子图的图像窗口,`subplot(1,2,1)`创建了第...