# Pure Bit Operation Solution Using Bit Field in C, Faster than Loop 32 Times.

• #Code:
typedef struct a_char{
char a1:4;
char a2:4;
}ACHAR;
char map[16]={0x0,0x8,0x4,0xc,0x2,0xa,0x6,0xe,0x1,0x9,0x5,0xd,0x3,0xb,0x7,0xf};
//char map[16]={0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};
size_t reverseBits1(size_t n) {
ACHAR *origin = (ACHAR *)&n;
ACHAR result[4];
for(int i=0;i<4;i++){
result[3-i].a2 = map[0xF&origin[i].a1];
result[3-i].a1= map[0xF&origin[i].a2];
}
return (size_t)result;
}

##Explanation on map[ ]:

• `0 = 0x0000`->`0x0000 = 0x0 = 0`
• `1 = 0x0001`->`0x1000 = 0x8 = 8`
• ......
• `7 = 0x0111`->`0x1110 = 0xE = 14`
• ......

#I compared the above solution with the loop version:

``````size_t reverseBits2(size_t n) {
int i;
size_t res = 0;
for(i = 0; i < 32; i++) {
res = (res << 1) ^ (n & 1);
n >>= 1;
}
return res;
}
``````

##The result proved that bit field version is faster.(costs only 60% time)

• reverseBits1(): 650 ms
• reverseBits2(): 1000 ms

##Test code:(You can run it in VS)

``````typedef struct a_char{
char a1:4;
char a2:4;
}ACHAR;
char map[16]={0x0,0x8,0x4,0xc,0x2,0xa,0x6,0xe,0x1,0x9,0x5,0xd,0x3,0xb,0x7,0xf};
size_t reverseBits1(size_t n) {
ACHAR *origin = (ACHAR *)&n;
ACHAR result[4];
for(int i=0;i<4;i++){
result[3-i].a2 = map[0xF&origin[i].a1];
result[3-i].a1= map[0xF&origin[i].a2];
}
return *(size_t*)result;
}
size_t reverseBits2(size_t n) {
int i;
size_t res = 0;
for(i = 0; i < 32; i++) {
res = (res << 1) ^ (n & 1);
n >>= 1;
}
return res;
}
#include <time.h>
int main(){
int ret;
clock_t start = clock();
for(int i=0;i<9999999;i++)
ret = reverseBits1(i);
clock_t end = clock();
clock_t start2 = clock();
for(int i=0;i<9999999;i++)
ret = reverseBits2(i);
clock_t end2 = clock();
return 0;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.