c语言练习题81：颠倒二进制位

颠倒二进制位

颠倒给定的 32 位⽆符号整数的⼆进制位。

提⽰： 请注意，在某些语⾔（如 Java）中，没有⽆符号整数类型。在这种情况下，输⼊和输出都将被指定为 有符号整数类型，并且不应影响您的实现，因为⽆论整数是有符号的还是⽆符号的，其内部的⼆进制 表⽰形式都是相同的。

在 Java 中，编译器使⽤⼆进制补码记法来表⽰有符号整数。因此，在 ⽰例 2 中，输⼊表⽰有符号整 数 -3，输出表⽰有符号整数 -1073741825。

• ⽰例 1：

输⼊：

n = 00000010100101000001111010011100

输出：964176192 (00111001011110000010100101000000)

解释：输⼊的⼆进制串 00000010100101000001111010011100 表⽰⽆符号整数 43261596， 因此返回 964176192，其⼆进制表⽰形式为 00111001011110000010100101000000。

• ⽰例 2：

输⼊：

n = 11111111111111111111111111111101

输出：

3221225471 (10111111111111111111111111111111)

解释：输⼊的⼆进制串 11111111111111111111111111111101 表⽰⽆符号整数 4294967293， 因此返回 3221225471 其⼆进制表⽰形式为 10111111111111111111111111111111 。

• 提⽰： 输⼊是⼀个⻓度为 32 的⼆进制字符串

解法（位运算）：

在 C/C++ 语⾔中， uint32_t 是⼀种⽆符号整型的数据类型，它表⽰的是⼀个 32 位的⽆符号整 数。其中，“uint” 表⽰“unsigned integer”，即⽆符号整型，⽽“32”表⽰该数据类型占⽤的 位数为 32 位。 由于⽆符号整型只能表⽰⾮负整数，因此 uint32_t 能表⽰的最⼤值为 2^32-1，即 4294967295，⽽最⼩值为 0。使⽤ uint32_t 可以确保变量在内存中占⽤的字节数为 4 字节，从 ⽽保证数据类型的可移植性。

本题规定了数的位数为 32 位，因此，我们可以从低位往⾼位依次遍历原数，并将其⾼位往低位赋值 给新的数。

算法思路：

1. 定义⼀个⽆符号整型变量 ans ，并初始化为 0。

2. 从低位到⾼位遍历原数的每⼀位。对于原数的第 i 位，我们将其右移 i-1 位后和 1 进⾏与运算， 得到它在第 i 位的值。

3. 将得到的值左移 31-i+1 位，得到其实际应该放置的位置。

4. 将原数的第 i 位的值赋值给 ans 的第 32-i+1 位。 • 需要注意的是，第⼀位的权值为 2^0，因此在计算时需要考虑实际左移和右移的位数。

uint32_t reverseBits(uint32_t n) {
	int i = 0;
	uint32_t ans = 0;
	for (i = 0; i <= 32; i++) {
		ans |= ((n >> (i = 1)) & 1) << (31 - i + 1);
		     //((n >> (i - 1)) & 1) << (31 - i + 1)
	}
	return ans;
}