LeetCode Q190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

My solution:

	class Solution {
	public:
	uint32_t reverseBits(uint32_t _n) {
	int p0=0;
	int p1=31;
	uint32_t n = _n;
	while(p0<=p1){
	int b0 = n>>p0 & 1;
	int b1 = n>>p1 & 1;
	if(b0==1)
	n = n | b0<<p1;
	else
	n = n & ~(1<<p1);
	if(b1==1)
	n = n | b1<<p0;
	else
	n = n & ~(1<<p0);
	p0++;
	p1--;
	}
	return n;
	}
	};

view raw Q190ReverseBits.cpp hosted with ❤ by GitHub

A cool solution using divide and conquer you should not miss!

	class Solution {
	public:
	uint32_t reverseBits(uint32_t n) {
	n = (n >> 16) | (n << 16);
	n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
	n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
	n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
	n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
	return n;
	}
	};

view raw Q190-2.cpp hosted with ❤ by GitHub

Another solution you have to know !

	uint32_t reverseBits(uint32_t n) {
	uint32_t m = 0;
	for (int i = 0; i < 32; i++, n >>= 1) {
	m <<= 1;
	m |= n & 1;
	}
	return m;
	}

view raw Q190-2.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	uint32_t reverseBits(uint32_t n) {
	for(int i=0; i<=15; i++){
	int p0 = i;
	int p1 = 31-i;
	if(((n>>p0)&1)^((n>>p1)&1)){
	n = (1<<p0)^n;
	n = (1<<p1)^n;
	}
	}
	return n;
	}
	};

view raw Q190Rnd2.cpp hosted with ❤ by GitHub