190. 颠倒二进制位

问题190 颠倒二进制位 ★☆☆☆☆

https://leetcode-cn.com/problems/reverse-bits/

这个题目的解题思路很直接，通过右移循环取出最低位的二进制位，然后通过左移累积结果值即可。

那么题目额外提出的，如果涉及大量调用，如何优化效率呢？一开始我没什么思路，看了一下官方题解，这个所谓的“位运算分治”，看描述还好理解，但是代码看不懂……

我又思考了下，既然要提高效率，那就每次多处理几位嘛。比如，每次取最低位的2位二进制位，这样循环次数就减少了一半，但是需要注意，累计结果值时，需要把取到的2位二进制翻转。那么有什么办法能快速翻转2位二进制位呢？一开始我的入手点是有没有什么二进制运算能完成，但是直觉上这是条死路。转念一想，直接弄个mapping就可以了嘛，把00,01,10,11对应的翻转存到数组里。进一步的，既然可以每次取最低位的2位，那么干脆更进一步，每次取最低位的4位呢？这样循环次数进一步减少，4位二进制位对应的mapping数组也不难处理。那么，还能进一步每次取最低位的8位吗？额，那就得维护一个包含256个元素的mapping数组了，感觉有点没必要了。

	private int[] mapping = {0b0000, 0b1000, 0b0100, 0b1100, 0b0010, 0b1010, 0b0110, 0b1110,
							 0b0001, 0b1001, 0b0101, 0b1101, 0b0011, 0b1011, 0b0111, 0b1111};

	public int reverseBits(int n) {
		int ret = 0;

		for (int i = 0; i < 8; i++) {
			int rightest4Bits = n & 15;
			n = n >> 4;
			ret = ret << 4;
			ret = ret | mapping[rightest4Bits];
		}

		return ret;
	}

在 LeetCode 查看