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


  • 1
    Y

    #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;
    }

Log in to reply
 

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