दिलचस्प पोस्ट
NHibernate इएसशन फ्लश: इसका उपयोग कब और कब किया जाए, और क्यों? डी 3 में "क्लिक करें" ईवेंट प्रोग्राम को कैसे खोलें? समवर्ती प्रोग्रामिंग और समानांतर प्रोग्रामिंग के बीच अंतर क्या है? माता-पिता की ऊँचाई को निर्दिष्ट किए बिना माता-पिता के div के 100% बच्चों को कैसे लागू करें? एचटीटीपी क्लाइंट 4.0.1 – कनेक्शन कैसे रिलीज करना है? इनपुट से पीएसपी लिखने के लिए फ़ाइल txt ओपन एक्सएल को होमब्रे के साथ ओएस एक्स पर अपडेट करें ओपनसीवी 2.3 कंपाइलिंग इशू – अपरिभाषित रिफेंस – उबंटू 11.10 किसी नक्शे से फिर से चलना और हटाना RootViewController एनीमेशन संक्रमण, प्रारंभिक ओरिएंटेशन गलत है सी ++ में उचित ढेर और ढेर का उपयोग? IPhone के लिए स्वचालित परीक्षण * .bat एक्सटेंशन का उपयोग करके बैच स्क्रिप्ट को कैसे चलाएं CollapsingToolbarLayout उपशीर्षक जावास्क्रिप्ट में ऑब्जेक्ट के एक सरणी को क्लोन कैसे करें?

बिट रिवर्सल (एमएसबी-> एलएसबी से एलएसबी-> एमएसबी) के लिए सबसे प्रभावी एल्गोरिथ्म सी में

निम्न प्राप्त करने के लिए सबसे अच्छा एल्गोरिथ्म क्या है:

0010 0000 => 0000 0100

रूपांतरण एमएसबी-> एलएसबी से एलएसबी-> एमएसबी से है सभी बिट उलट होनी चाहिए; यही है, यह अंतहीनता-गमागमन नहीं है

वेब के समाधान से एकत्रित समाधान "बिट रिवर्सल (एमएसबी-> एलएसबी से एलएसबी-> एमएसबी) के लिए सबसे प्रभावी एल्गोरिथ्म सी में"

नोट : नीचे दिए गए सभी एल्गोरिदम सी में हैं, लेकिन आपकी पसंद की भाषा के लिए पोर्टेबल होना चाहिए (जब वे तेज़ी से नहीं होते हैं तो मुझे न देखें)

विकल्प

कम मेमोरी (32-बिट int , 32-बिट मशीन) ( यहां से ):

 unsigned int reverse(register unsigned int x) { x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); } 

प्रसिद्ध बिट ट्विडिंग हैक्स पेज से :

सबसे तेज (लुकअप तालिका) :

 static const unsigned char BitReverseTable256[] = { 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF }; unsigned int v; // reverse 32-bit value, 8 bits at time unsigned int c; // c will get v reversed // Option 1: c = (BitReverseTable256[v & 0xff] << 24) | (BitReverseTable256[(v >> 8) & 0xff] << 16) | (BitReverseTable256[(v >> 16) & 0xff] << 8) | (BitReverseTable256[(v >> 24) & 0xff]); // Option 2: unsigned char * p = (unsigned char *) &v; unsigned char * q = (unsigned char *) &c; q[3] = BitReverseTable256[p[0]]; q[2] = BitReverseTable256[p[1]]; q[1] = BitReverseTable256[p[2]]; q[0] = BitReverseTable256[p[3]]; 

आप इस विचार को 64-बिट int को बढ़ा सकते हैं, या गति के लिए व्यापार बंद मेमोरी (आपके एल 1 डाटा कैश संभालने के लिए काफी बड़ा है), और 64-के-प्रवेश लुकअप तालिका के साथ एक समय में 16-बिट रिवर्स कर सकते हैं।


अन्य लोग

सरल

 unsigned int v; // input bits to be reversed unsigned int r = v & 1; // r will be reversed bits of v; first get LSB of v int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end for (v >>= 1; v; v >>= 1) { r <<= 1; r |= v & 1; s--; } r <<= s; // shift when v's highest bits are zero 

तेज़ (32-बिट प्रोसेसर)

 unsigned char b = x; b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

तेज़ (64-बिट प्रोसेसर)

 unsigned char b; // reverse this (8-bit) byte b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023; 

यदि आप इसे 32-बिट int पर करना चाहते हैं, तो प्रत्येक बाइट्स में बिट्स को उलट करें और बाइट्स के क्रम को उलट दें। अर्थात्:

 unsigned int toReverse; unsigned int reversed; unsigned char inByte0 = (toReverse & 0xFF); unsigned char inByte1 = (toReverse & 0xFF00) >> 8; unsigned char inByte2 = (toReverse & 0xFF0000) >> 16; unsigned char inByte3 = (toReverse & 0xFF000000) >> 24; reversed = (reverseBits(inByte0) << 24) | (reverseBits(inByte1) << 16) | (reverseBits(inByte2) << 8) | (reverseBits(inByte3); 

परिणाम

मैंने दो सबसे आशाजनक समाधान, लुकअप तालिका और बिटवर्ड-और (पहले एक) को बेंचमार्क किया था। परीक्षण मशीन एक लैपटॉप वाई / 4 जीबी डीडीआर 2-800 और एक कोर 2 डुओ टी 7500 @ 2.4GHz, 4 एमबी एल 2 कैशे है; YMMV। मैं 64-बिट लिनक्स पर जीसीसी 4.3.2 का इस्तेमाल किया। ओपनएमपी (और जीसीसी बाइंडिंग) का इस्तेमाल उच्च रिज़ॉल्यूशन टाइमर के लिए किया गया था।

reverse.c

 #include <stdlib.h> #include <stdio.h> #include <omp.h> unsigned int reverse(register unsigned int x) { x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); } int main() { unsigned int *ints = malloc(100000000*sizeof(unsigned int)); unsigned int *ints2 = malloc(100000000*sizeof(unsigned int)); for(unsigned int i = 0; i < 100000000; i++) ints[i] = rand(); unsigned int *inptr = ints; unsigned int *outptr = ints2; unsigned int *endptr = ints + 100000000; // Starting the time measurement double start = omp_get_wtime(); // Computations to be measured while(inptr != endptr) { (*outptr) = reverse(*inptr); inptr++; outptr++; } // Measuring the elapsed time double end = omp_get_wtime(); // Time calculation (in seconds) printf("Time: %f seconds\n", end-start); free(ints); free(ints2); return 0; } 

reverse_lookup.c

 #include <stdlib.h> #include <stdio.h> #include <omp.h> static const unsigned char BitReverseTable256[] = { 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF }; int main() { unsigned int *ints = malloc(100000000*sizeof(unsigned int)); unsigned int *ints2 = malloc(100000000*sizeof(unsigned int)); for(unsigned int i = 0; i < 100000000; i++) ints[i] = rand(); unsigned int *inptr = ints; unsigned int *outptr = ints2; unsigned int *endptr = ints + 100000000; // Starting the time measurement double start = omp_get_wtime(); // Computations to be measured while(inptr != endptr) { unsigned int in = *inptr; // Option 1: //*outptr = (BitReverseTable256[in & 0xff] << 24) | // (BitReverseTable256[(in >> 8) & 0xff] << 16) | // (BitReverseTable256[(in >> 16) & 0xff] << 8) | // (BitReverseTable256[(in >> 24) & 0xff]); // Option 2: unsigned char * p = (unsigned char *) &(*inptr); unsigned char * q = (unsigned char *) &(*outptr); q[3] = BitReverseTable256[p[0]]; q[2] = BitReverseTable256[p[1]]; q[1] = BitReverseTable256[p[2]]; q[0] = BitReverseTable256[p[3]]; inptr++; outptr++; } // Measuring the elapsed time double end = omp_get_wtime(); // Time calculation (in seconds) printf("Time: %f seconds\n", end-start); free(ints); free(ints2); return 0; } 

मैंने कई अलग-अलग अनुकूलन में दोनों तरीकों की कोशिश की, प्रत्येक स्तर पर 3 परीक्षण चलाए, और प्रत्येक मुकदमा 100 मिलियन यादृच्छिक अहस्ताक्षरित इनट उलट गया। लुकअप तालिका विकल्प के लिए, मैंने bitwise hacks पृष्ठ पर दिए गए दोनों योजनाओं (विकल्प 1 और 2) की कोशिश की। परिणाम नीचे दिखाए गए हैं

Bitwise और

 mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse reverse.c mrj10@mjlap:~/code$ ./reverse Time: 2.000593 seconds mrj10@mjlap:~/code$ ./reverse Time: 1.938893 seconds mrj10@mjlap:~/code$ ./reverse Time: 1.936365 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse reverse.c mrj10@mjlap:~/code$ ./reverse Time: 0.942709 seconds mrj10@mjlap:~/code$ ./reverse Time: 0.991104 seconds mrj10@mjlap:~/code$ ./reverse Time: 0.947203 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse reverse.c mrj10@mjlap:~/code$ ./reverse Time: 0.922639 seconds mrj10@mjlap:~/code$ ./reverse Time: 0.892372 seconds mrj10@mjlap:~/code$ ./reverse Time: 0.891688 seconds 

लुकअप टेबल (विकल्प 1)

 mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.201127 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.196129 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.235972 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.633042 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.655880 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.633390 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.652322 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.631739 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.652431 seconds 

लुकअप टेबल (विकल्प 2)

 mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.671537 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.688173 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.664662 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.049851 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.048403 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.085086 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.082223 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.053431 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.081224 seconds 

निष्कर्ष

लुकअप तालिका का उपयोग करें, विकल्प 1 (बाइट एड्रेसिंग अशुभ रूप से धीमा है) के साथ यदि आप प्रदर्शन के बारे में चिंतित हैं यदि आपको अपने सिस्टम से स्मृति के हर अंतिम बाइट को निचोड़ने की आवश्यकता है (और यदि आप थोड़ा उलट के प्रदर्शन के बारे में सोचते हैं, तो शायद), बिटवर्ड- और दृष्टिकोण के अनुकूलित संस्करण भी बहुत गड़बड़ नहीं हैं।

चेतावनी

हां, मुझे पता है बेंचमार्क कोड एक पूर्ण हैक है इसे सुधारने के बारे में सुझाव स्वागत के मुकाबले ज्यादा हैं जिन चीज़ों के बारे में मुझे पता है:

  • मेरे पास आईसीसी तक पहुंच नहीं है I यह तेज़ हो सकता है (यदि आप इसका परीक्षण कर सकते हैं तो कृपया टिप्पणी में जवाब दें)
  • एक 64K लुकअप तालिका बड़े एल 1 डी के साथ कुछ आधुनिक माइक्रोआर्किटेक्चर्स पर अच्छा प्रदर्शन कर सकती है।
  • -एमटीन = देशी -O2 / -O3 के लिए काम नहीं किया ( ld कुछ पागल प्रतीकों redefinition त्रुटि के साथ उड़ा दिया), इसलिए मुझे विश्वास नहीं है कि मेरे माइक्रोआर्किटेक्चर के लिए उत्पन्न कोड ट्यून किया गया है।
  • एसएसई के साथ थोड़ी तेजी से ऐसा करने का एक तरीका हो सकता है। मुझे नहीं पता कि कैसे, लेकिन तेजी से प्रतिकृति के साथ, पैक किए गए बिटwise और, और स्विजिंग निर्देशों के साथ, वहाँ कुछ होना चाहिए।
  • मुझे पता है कि पर्याप्त एक्स 86 विधानसभा खतरनाक है; यहां विकल्प 1 के लिए ऑब्जेक्ट पर जीसीसी कोड तैयार किया गया है, इसलिए किसी की तुलना में किसी और को ज्यादा जानकारियां इसे देख सकती हैं:

32-बिट

 .L3: movl (%r12,%rsi), %ecx movzbl %cl, %eax movzbl BitReverseTable256(%rax), %edx movl %ecx, %eax shrl $24, %eax mov %eax, %eax movzbl BitReverseTable256(%rax), %eax sall $24, %edx orl %eax, %edx movzbl %ch, %eax shrl $16, %ecx movzbl BitReverseTable256(%rax), %eax movzbl %cl, %ecx sall $16, %eax orl %eax, %edx movzbl BitReverseTable256(%rcx), %eax sall $8, %eax orl %eax, %edx movl %edx, (%r13,%rsi) addq $4, %rsi cmpq $400000000, %rsi jne .L3 

संपादित करें: मैंने अपने मशीन पर यूआईटी 64_ टी का उपयोग करने की भी कोशिश की, ताकि यह देखने के लिए कि क्या कोई प्रदर्शन बढ़ाने वाला है। निष्पादन 32-बिट की तुलना में लगभग 10% तेज था, और लगभग समान था कि क्या आप 64-बिट प्रकारों का उपयोग केवल एक समय में दो 32-बिट इनट्स पर बिट्स को रिवर्स करने के लिए कर रहे थे, या आप वास्तव में 64 बिट के रूप में आधे बिट में पीछे थे, बिट मान विधानसभा कोड नीचे दिखाया गया है (पूर्व मामले के लिए, एक बार में 2 32-बिट इनट्स के लिए बिट्स को पीछे करने वाला):

 .L3: movq (%r12,%rsi), %rdx movq %rdx, %rax shrq $24, %rax andl $255, %eax movzbl BitReverseTable256(%rax), %ecx movzbq %dl,%rax movzbl BitReverseTable256(%rax), %eax salq $24, %rax orq %rax, %rcx movq %rdx, %rax shrq $56, %rax movzbl BitReverseTable256(%rax), %eax salq $32, %rax orq %rax, %rcx movzbl %dh, %eax shrq $16, %rdx movzbl BitReverseTable256(%rax), %eax salq $16, %rax orq %rax, %rcx movzbq %dl,%rax shrq $16, %rdx movzbl BitReverseTable256(%rax), %eax salq $8, %rax orq %rax, %rcx movzbq %dl,%rax shrq $8, %rdx movzbl BitReverseTable256(%rax), %eax salq $56, %rax orq %rax, %rcx movzbq %dl,%rax shrq $8, %rdx movzbl BitReverseTable256(%rax), %eax andl $255, %edx salq $48, %rax orq %rax, %rcx movzbl BitReverseTable256(%rdx), %eax salq $40, %rax orq %rax, %rcx movq %rcx, (%r13,%rsi) addq $8, %rsi cmpq $400000000, %rsi jne .L3 

इस थ्रेड ने मेरी ओर ध्यान आकर्षित किया क्योंकि यह एक साधारण समस्या से संबंधित है जो कि एक आधुनिक सीपीयू के लिए बहुत सारे काम (CPU चक्र) की आवश्यकता होती है और एक दिन मैं वही ¤ #% "#" समस्या के साथ वहां भी खड़ा था मुझे लाखों बाइट्स को फ्लिप करना था। हालांकि मुझे पता है कि मेरे सारे लक्ष्य सिस्टम आधुनिक इंटेल हैं, इसलिए हम चरम के अनुकूलन शुरू कर देते हैं !!!

इसलिए मैंने मैट जे का लुकअप कोड बेस के रूप में प्रयोग किया था। जिस प्रणाली पर मैं बेंचमार्किंग कर रहा हूं I7 हैव 4700 एक्यू है I

मैट जे के लुकअप में 400 000 000 बाइट्स फिसलने हैं: लगभग 0.272 सेकंड।

मैं तो आगे चला गया और यह देखने की कोशिश की कि क्या Intels ISPC कंपाइलर रिवर्स सी में गणित को सदिश कर सकता है।

मैं आपको अपने निष्कर्षों के साथ बोर नहीं जाऊंगा क्योंकि मैं कम्पाइलर खोज सामान की मदद करने के लिए बहुत कुछ करने की कोशिश कर रहा था, किसी भी तरह मैं 0.15 सेकंड के प्रदर्शन के साथ समाप्त हो गया था और 400 000 000 बाइट्सप्लिप्स बिट्स हो गया था। यह एक महान कमी है, लेकिन मेरे आवेदन के लिए जो अब भी धीमा करने का तरीका है ..

तो लोग मुझे दुनिया में सबसे तेजी से इंटेल आधारित bitflipper प्रस्तुत करते हैं इस पर क्लॉक किया गया:

400000000 बाइट्स बिटस्ट्रैप करने का समय: 0.050082 सेकंड !!!!!

 // Bitflip using AVX2 - The fastest Intel based bitflip in the world!! // Made by Anders Cedronius 2014 (anders.cedronius (you know what) gmail.com) #include <stdio.h> #include <stdlib.h> #include <math.h> #include <omp.h> using namespace std; #define DISPLAY_HEIGHT 4 #define DISPLAY_WIDTH 32 #define NUM_DATA_BYTES 400000000 // Constants (first we got the mask, then the high order nibble look up table and last we got the low order nibble lookup table) __attribute__ ((aligned(32))) static unsigned char k1[32*3]={ 0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f, 0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f, 0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0 }; // The data to be bitflipped (+32 to avoid the quantization out of memory problem) __attribute__ ((aligned(32))) static unsigned char data[NUM_DATA_BYTES+32]={}; extern "C" { void bitflipbyte(unsigned char[],unsigned int,unsigned char[]); } int main() { for(unsigned int i = 0; i < NUM_DATA_BYTES; i++) { data[i] = rand(); } printf ("\r\nData in(start):\r\n"); for (unsigned int j = 0; j < 4; j++) { for (unsigned int i = 0; i < DISPLAY_WIDTH; i++) { printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]); } printf ("\r\n"); } printf ("\r\nNumber of 32-byte chunks to convert: %d\r\n",(unsigned int)ceil(NUM_DATA_BYTES/32.0)); double start_time = omp_get_wtime(); bitflipbyte(data,(unsigned int)ceil(NUM_DATA_BYTES/32.0),k1); double end_time = omp_get_wtime(); printf ("\r\nData out:\r\n"); for (unsigned int j = 0; j < 4; j++) { for (unsigned int i = 0; i < DISPLAY_WIDTH; i++) { printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]); } printf ("\r\n"); } printf("\r\n\r\nTime to bitflip %d bytes: %f seconds\r\n\r\n",NUM_DATA_BYTES, end_time-start_time); // return with no errors return 0; } 

डिबगिंग के लिए प्रिटफ़ का ..

यहां कार्यक्षेत्र है:

 bits 64 global bitflipbyte bitflipbyte: vmovdqa ymm2, [rdx] add rdx, 20h vmovdqa ymm3, [rdx] add rdx, 20h vmovdqa ymm4, [rdx] bitflipp_loop: vmovdqa ymm0, [rdi] vpand ymm1, ymm2, ymm0 vpandn ymm0, ymm2, ymm0 vpsrld ymm0, ymm0, 4h vpshufb ymm1, ymm4, ymm1 vpshufb ymm0, ymm3, ymm0 vpor ymm0, ymm0, ymm1 vmovdqa [rdi], ymm0 add rdi, 20h dec rsi jnz bitflipp_loop ret 

कोड 32 बाइट लेता है तो मास्क को निबल्स से बाहर निकालता है। उच्च चोंच सही 4 से स्थानांतरित हो जाता है। फिर मैं लुकअप तालिकाओं के रूप में vpshufb और ymm4 / ymm3 का उपयोग करें। मैं एक एकल लुकअप तालिका का उपयोग कर सकता था लेकिन फिर मुझे एक साथ फिर से nibbles को संगठित करने से पहले बाएं पारी पाना होगा।

बिट्स को फ्लिप करने के तेज तरीके भी हैं। लेकिन मैं एकल थ्रेड और सीपीयू के लिए बाध्य हूं, इसलिए यह सबसे तेज मैं हासिल कर सकता था। क्या आप एक तेज संस्करण बना सकते हैं?

कृपया इंटेल सी / सी + + कंपाइलर इंट्रिनिसिक समतुल्य आदेशों का उपयोग करने के बारे में कोई टिप्पणी नहीं करें …

यह उन लोगों के लिए दूसरा समाधान है जो पुनरावृत्ति को पसंद करते हैं।

विचार सरल है आधे से इनपुट को विभाजित करें और दो हिस्सों को स्वैप करें, तब तक जारी रखें जब तक यह एक बिट तक नहीं पहुंचता।

 Illustrated in the example below. Ex : If Input is 00101010 ==> Expected output is 01010100 1. Divide the input into 2 halves 0010 --- 1010 2. Swap the 2 Halves 1010 0010 3. Repeat the same for each half. 10 -- 10 --- 00 -- 10 10 10 10 00 1-0 -- 1-0 --- 1-0 -- 0-0 0 1 0 1 0 1 0 0 Done! Output is 01010100 

इसे हल करने के लिए एक पुनरावर्ती समारोह है। (नोट मैंने अहस्ताक्षरित इनट का इस्तेमाल किया है, इसलिए यह आकार के आकार (अहस्ताक्षरित पूर्णांक) * 8 बिट तक इनपुट के लिए काम कर सकता है।

रिकर्सिव फ़ंक्शन 2 पैरामीटर लेता है – मान जिसका बिट्स को उलट किया जाना चाहिए और मूल्य में बिट्स की संख्या।

 int reverse_bits_recursive(unsigned int num, unsigned int numBits) { unsigned int reversedNum;; unsigned int mask = 0; mask = (0x1 << (numBits/2)) - 1; if (numBits == 1) return num; reversedNum = reverse_bits_recursive(num >> numBits/2, numBits/2) | reverse_bits_recursive((num & mask), numBits/2) << numBits/2; return reversedNum; } int main() { unsigned int reversedNum; unsigned int num; num = 0x55; reversedNum = reverse_bits_recursive(num, 8); printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum); num = 0xabcd; reversedNum = reverse_bits_recursive(num, 16); printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum); num = 0x123456; reversedNum = reverse_bits_recursive(num, 24); printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum); num = 0x11223344; reversedNum = reverse_bits_recursive(num,32); printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum); } 

यह आउटपुट है:

 Bit Reversal Input = 0x55 Output = 0xaa Bit Reversal Input = 0xabcd Output = 0xb3d5 Bit Reversal Input = 0x123456 Output = 0x651690 Bit Reversal Input = 0x11223344 Output = 0x22cc4488 

वैसे यह निश्चित रूप से मैट जे की तरह एक जवाब नहीं होगा, लेकिन उम्मीद है कि यह अभी भी उपयोगी होगा।

 size_t reverse(size_t n, unsigned int bytes) { __asm__("BSWAP %0" : "=r"(n) : "0"(n)); n >>= ((sizeof(size_t) - bytes) * 8); n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1); n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2); n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4); return n; } 

यह मैट के सर्वश्रेष्ठ एल्गोरिदम के समान ही एक विचार है, सिवाय इसके कि इस छोटे से निर्देश बीएसडब्ल्यूएपी हैं जो 64-बिट नंबर के बाइट्स (बिट्स नहीं) को स्वैप करता है। तो बी 7, बी 6, बी 5, बी 4, बी 3, बी 2, बी 1, बी 0 बी0, बी 1, बी 2, बी 3, बी 4, बी 5, बी 6, बी 7 हो। चूंकि हम एक 32-बिट संख्या के साथ काम कर रहे हैं इसलिए हमें 32 बिट्स के नीचे हमारी बाइट-बदली संख्या बदलनी होगी। यह सिर्फ हमारे द्वारा प्रत्येक बाइट के 8 बिट्स को गमागमन करने का कार्य छोड़ देता है जो कि किया जाता है और वोला! हो गया था।

समय: मेरी मशीन पर, मैट के एल्गोरिथम में प्रति परीक्षण ~ 0.52 सेकंड चल पड़ा। मेरा परीक्षण लगभग 0.42 सेकेंड में था। 20% तेजी से मुझे लगता है बुरा नहीं है।

यदि आप निर्देश की उपलब्धता के बारे में चिंतित हैं तो बीएसडब्ल्यूएपी विकिपीडिया ने बीएसडब्ल्यूएपी के निर्देश को सूची में सूचीबद्ध किया है, जैसा कि 1 9 8 9 में 80846 से जोड़ा गया था। यह ध्यान दिया जाना चाहिए कि विकिपीडिया यह भी बताता है कि यह निर्देश केवल 32 बिट रजिस्टरों पर काम करता है जो स्पष्ट रूप से नहीं है मेरी मशीन पर मामला है, यह बहुत ही 64-बिट रजिस्टरों पर काम करता है।

यह विधि किसी भी अभिन्न डेटाटाइप के लिए समान रूप से अच्छी तरह से काम करेगी ताकि वांछित बाइट्स की संख्या को पार करके विधि को सामान्य रूप से सामान्य किया जा सके:

  size_t reverse(size_t n, unsigned int bytes) { __asm__("BSWAP %0" : "=r"(n) : "0"(n)); n >>= ((sizeof(size_t) - bytes) * 8); n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1); n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2); n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4); return n; } 

जिसे बाद में कहा जा सकता है:

  n = reverse(n, sizeof(char));//only reverse 8 bits n = reverse(n, sizeof(short));//reverse 16 bits n = reverse(n, sizeof(int));//reverse 32 bits n = reverse(n, sizeof(size_t));//reverse 64 bits 

कंपाइलर अतिरिक्त पैरामीटर को दूर करने में सक्षम होना चाहिए (संकलक को कार्यप्रणाली को इंगित करता है) और sizeof(size_t) के sizeof(size_t) मामले में सही-शिफ्ट को पूरी तरह से हटा दिया जाएगा। ध्यान दें कि जीसीसी कम से कम बीएसडब्ल्यूएपी और सही-शिफ्ट को पारित करने में सक्षम नहीं है, यदि पारित किया गया sizeof(char)

यह मानते हुए कि आपके पास बिट्स की एक सरणी है, इस बारे में कैसे: 1. MSB से शुरू, बिट्स को स्टैक में एक करके एक करके दबाएं। 2. इस स्टैक से दूसरे बिट (या यदि आप को स्थान बचाने के लिए चाहते हैं) में इस स्टैक में पॉप बिट्स, पहले बीता हुआ बिट को MSB में रखकर और वहां से कम महत्वपूर्ण बिट्स पर जा रहे हैं।

 Stack stack = new Stack(); Bit[] bits = new Bit[] { 0, 0, 1, 0, 0, 0, 0, 0 }; for (int i = 0; i < bits.Length; i++) { stack.push(bits[i]); } for (int i = 0; i < bits.Length; i++) { bits[i] = stack.pop(); } 

ऐन्डर्स सेड्रोनियस का उत्तर उन लोगों के लिए एक महान समाधान प्रदान करता है जिनके पास एक्सएक्स 2 समर्थन के साथ एक x86 सीपीयू है। एक्सएक्स समर्थन या गैर एक्स 86 प्लेटफार्मों के बिना एक्स 86 प्लेटफार्मों के लिए, निम्न कार्यान्वयनों में से कोई भी ठीक से काम करना चाहिए।

पहला कोड क्लासिक द्विआधारी विभाजन पद्धति का एक रूप है, जो विभिन्न एआरएम प्रोसेसर पर बदलाव-प्लस-लॉजिक मुहावरों के उपयोग को अधिकतम करने के लिए कोडित है। इसके अलावा, यह पर-फ्लाई मास्क पीढ़ी का उपयोग करता है जो कि आरआईएससी प्रोसेसर के लिए फायदेमंद हो सकता है, अन्यथा प्रत्येक 32-बिट मुखौटा मूल्य को लोड करने के लिए कई निर्देशों की आवश्यकता होती है। X86 प्लेटफार्म के लिए कम्पाइलर को समय के बजाय संकलन समय पर सभी मुखौटे की गणना करने के लिए लगातार प्रचार का उपयोग करना चाहिए।

 /* Classic binary partitioning algorithm */ inline uint32_t brev_classic (uint32_t a) { uint32_t m; a = (a >> 16) | (a << 16); // swap halfwords m = 0x00ff00ff; a = ((a >> 8) & m) | ((a << 8) & ~m); // swap bytes m = m^(m << 4); a = ((a >> 4) & m) | ((a << 4) & ~m); // swap nibbles m = m^(m << 2); a = ((a >> 2) & m) | ((a << 2) & ~m); m = m^(m << 1); a = ((a >> 1) & m) | ((a << 1) & ~m); return a; } 

"कंप्यूटर प्रोग्रामिंग की कला" के वॉल्यूम 4 ए में, डी। न्यथ शास्त्रीय बाइनरी विभाजन एल्गोरिदम की तुलना में कुछ आश्चर्यजनक रूप से कम परिचालन की आवश्यकता के अनुसार बिट्स को पीछे करने के चालाक तरीके दिखाते हैं। 32-बिट ऑपरेंड के लिए ऐसा एक एल्गोरिथ्म, जो मुझे टीएओसीपी में नहीं मिल सकता है, हैकर डिलीइट वेबसाइट पर इस दस्तावेज़ में दिखाया गया है।

 /* Knuth's algorithm from http://www.hackersdelight.org/revisions.pdf. Retrieved 8/19/2015 */ inline uint32_t brev_knuth (uint32_t a) { uint32_t t; a = (a << 15) | (a >> 17); t = (a ^ (a >> 10)) & 0x003f801f; a = (t + (t << 10)) ^ a; t = (a ^ (a >> 4)) & 0x0e038421; a = (t + (t << 4)) ^ a; t = (a ^ (a >> 2)) & 0x22488842; a = (t + (t << 2)) ^ a; return a; } 

इंटेल कंपाइलर सी / सी ++ कंपाइलर 13.1.3.198 का ​​उपयोग करते हुए, XMM रजिस्टरों को अच्छी तरह से लक्षित करने के लिए, उपर्युक्त सभी कार्यों के ऑटो-वेक्टर को। बहुत प्रयास किए बिना उन्हें मैन्युअल रूप से वेक्टर किया जा सकता है

स्वत: vectorized कोड का उपयोग करते हुए, अपने IvyBridge Xeon E3 1270v2 पर, brev_classic() का उपयोग कर brev_classic() , और 0.068 सेकंड का उपयोग करते हुए 100 लाख uin32_t शब्द 0.070 सेकंड में थोड़ा उलट थे। मैंने यह सुनिश्चित करने के लिए ध्यान रखा था कि मेरा बेंचमार्क सिस्टम मेमोरी बैंडविड्थ तक सीमित नहीं था

मुझे पता है कि यह सी नहीं है, लेकिन asm:

 var1 dw 0f0f0 clc push ax push cx mov cx 16 loop1: shl var1 shr ax loop loop1 pop ax pop cx 

यह ले जाने के साथ काम करता है, इसलिए आप झंडे को भी बचा सकते हैं

बेशक, बिट-ट्विडिंग हैक्स का स्पष्ट स्रोत यहां है: http://graphics.stanford.edu/~seander/bithacks.html#BitReverse जाहिर है

कम स्मृति और सबसे तेज़ी के साथ कार्यान्वयन

 private Byte BitReverse(Byte bData) { Byte[] lookup = { 0, 8, 4, 12, 2, 10, 6, 14 , 1, 9, 5, 13, 3, 11, 7, 15 }; Byte ret_val = (Byte)(((lookup[(bData & 0x0F)]) << 4) + lookup[((bData & 0xF0) >> 4)]); return ret_val; } 

आप मानक टेम्पलेट लाइब्रेरी का उपयोग करना चाहेंगे। यह उपर्युक्त कोड से धीमा हो सकता है। हालांकि, यह मुझे समझने में आसान और आसान लगता है।

  #include<bitset> #include<iostream> template<size_t N> const std::bitset<N> reverse(const std::bitset<N>& ordered) { std::bitset<N> reversed; for(size_t i = 0, j = N - 1; i < N; ++i, --j) reversed[j] = ordered[i]; return reversed; }; // test the function int main() { unsigned long num; const size_t N = sizeof(num)*8; std::cin >> num; std::cout << std::showbase << std::hex; std::cout << "ordered = " << num << std::endl; std::cout << "reversed = " << reverse<N>(num).to_ulong() << std::endl; std::cout << "double_reversed = " << reverse<N>(reverse<N>(num)).to_ulong() << std::endl; } 

This ain't no job for a human! … but perfect for a machine

This is 2015, 6 years from when this question was first asked. Compilers have since become our masters, and our job as humans is only to help them. So what's the best way to give our intentions to the machine?

Bit-reversal is so common that you have to wonder why the x86's ever growing ISA doesn't include an instruction to do it one go.

The reason: if you give your true concise intent to the compiler, bit reversal should only take ~20 CPU cycles . Let me show you how to craft reverse() and use it:

 #include <inttypes.h> #include <stdio.h> uint64_t reverse(const uint64_t n, const uint64_t k) { uint64_t r, i; for (r = 0, i = 0; i < k; ++i) r |= ((n >> i) & 1) << (k - i - 1); return r; } int main() { const uint64_t size = 64; uint64_t sum = 0; uint64_t a; for (a = 0; a < (uint64_t)1 << 30; ++a) sum += reverse(a, size); printf("%" PRIu64 "\n", sum); return 0; } 

Compiling this sample program with Clang version >= 3.6, -O3, -march=native (tested with Haswell), gives artwork-quality code using the new AVX2 instructions, with a runtime of 11 seconds processing ~1 billion reverse()s. That's ~10 ns per reverse(), with .5 ns CPU cycle assuming 2 GHz puts us at the sweet 20 CPU cycles.

  • You can fit 10 reverse()s in the time it takes to access RAM once for a single large array!
  • You can fit 1 reverse() in the time it takes to access an L2 cache LUT twice.

Caveat: this sample code should hold as a decent benchmark for a few years, but it will eventually start to show its age once compilers are smart enough to optimize main() to just printf the final result instead of really computing anything. But for now it works in showcasing reverse().

Native ARM instruction "rbit" can do it with 1 cpu cycle and 1 extra cpu register, impossible to beat.

Generic

C code. Using 1 byte input data num as example.

  unsigned char num = 0xaa; // 1010 1010 (aa) -> 0101 0101 (55) int s = sizeof(num) * 8; // get number of bits int i, x, y, p; int var = 0; // make var data type to be equal or larger than num for (i = 0; i < (s / 2); i++) { // extract bit on the left, from MSB p = s - i - 1; x = num & (1 << p); x = x >> p; printf("x: %d\n", x); // extract bit on the right, from LSB y = num & (1 << i); y = y >> i; printf("y: %d\n", y); var = var | (x << i); // apply x var = var | (y << p); // apply y } printf("new: 0x%x\n", new); 

How about the following:

  uint reverseMSBToLSB32ui(uint input) { uint output = 0x00000000; uint toANDVar = 0; int places = 0; for (int i = 1; i < 32; i++) { places = (32 - i); toANDVar = (uint)(1 << places); output |= (uint)(input & (toANDVar)) >> places; } return output; } 

Small and easy (though, 32 bit only).

I was curious how fast would be the obvious raw rotation. On my machine (i7@2600), the average for 1,500,150,000 iterations was 27.28 ns (over aa random set of 131,071 64-bit integers).

Advantages: the amount of memory needed is little and the code is simple. I would say it is not that large, either. The time required is predictable and constant for any input (128 arithmetic SHIFT operations + 64 logical AND operations + 64 logical OR operations).

I compared to the best time obtained by @Matt J – who has the accepted answer. If I read his answer correctly, the best he has got was 0.631739 seconds for 1,000,000 iterations, which leads to an average of 631 ns per rotation.

The code snippet I used is this one below:

 unsigned long long reverse_long(unsigned long long x) { return (((x >> 0) & 1) << 63) | (((x >> 1) & 1) << 62) | (((x >> 2) & 1) << 61) | (((x >> 3) & 1) << 60) | (((x >> 4) & 1) << 59) | (((x >> 5) & 1) << 58) | (((x >> 6) & 1) << 57) | (((x >> 7) & 1) << 56) | (((x >> 8) & 1) << 55) | (((x >> 9) & 1) << 54) | (((x >> 10) & 1) << 53) | (((x >> 11) & 1) << 52) | (((x >> 12) & 1) << 51) | (((x >> 13) & 1) << 50) | (((x >> 14) & 1) << 49) | (((x >> 15) & 1) << 48) | (((x >> 16) & 1) << 47) | (((x >> 17) & 1) << 46) | (((x >> 18) & 1) << 45) | (((x >> 19) & 1) << 44) | (((x >> 20) & 1) << 43) | (((x >> 21) & 1) << 42) | (((x >> 22) & 1) << 41) | (((x >> 23) & 1) << 40) | (((x >> 24) & 1) << 39) | (((x >> 25) & 1) << 38) | (((x >> 26) & 1) << 37) | (((x >> 27) & 1) << 36) | (((x >> 28) & 1) << 35) | (((x >> 29) & 1) << 34) | (((x >> 30) & 1) << 33) | (((x >> 31) & 1) << 32) | (((x >> 32) & 1) << 31) | (((x >> 33) & 1) << 30) | (((x >> 34) & 1) << 29) | (((x >> 35) & 1) << 28) | (((x >> 36) & 1) << 27) | (((x >> 37) & 1) << 26) | (((x >> 38) & 1) << 25) | (((x >> 39) & 1) << 24) | (((x >> 40) & 1) << 23) | (((x >> 41) & 1) << 22) | (((x >> 42) & 1) << 21) | (((x >> 43) & 1) << 20) | (((x >> 44) & 1) << 19) | (((x >> 45) & 1) << 18) | (((x >> 46) & 1) << 17) | (((x >> 47) & 1) << 16) | (((x >> 48) & 1) << 15) | (((x >> 49) & 1) << 14) | (((x >> 50) & 1) << 13) | (((x >> 51) & 1) << 12) | (((x >> 52) & 1) << 11) | (((x >> 53) & 1) << 10) | (((x >> 54) & 1) << 9) | (((x >> 55) & 1) << 8) | (((x >> 56) & 1) << 7) | (((x >> 57) & 1) << 6) | (((x >> 58) & 1) << 5) | (((x >> 59) & 1) << 4) | (((x >> 60) & 1) << 3) | (((x >> 61) & 1) << 2) | (((x >> 62) & 1) << 1) | (((x >> 63) & 1) << 0); } 

Well, this is basically the same as the first "reverse()" but it is 64 bit and only needs one immediate mask to be loaded from the instruction stream. GCC creates code without jumps, so this should be pretty fast.

 #include <stdio.h> static unsigned long long swap64(unsigned long long val) { #define ZZZZ(x,s,m) (((x) >>(s)) & (m)) | (((x) & (m))<<(s)); /* val = (((val) >>16) & 0xFFFF0000FFFF) | (((val) & 0xFFFF0000FFFF)<<16); */ val = ZZZZ(val,32, 0x00000000FFFFFFFFull ); val = ZZZZ(val,16, 0x0000FFFF0000FFFFull ); val = ZZZZ(val,8, 0x00FF00FF00FF00FFull ); val = ZZZZ(val,4, 0x0F0F0F0F0F0F0F0Full ); val = ZZZZ(val,2, 0x3333333333333333ull ); val = ZZZZ(val,1, 0x5555555555555555ull ); return val; #undef ZZZZ } int main(void) { unsigned long long val, aaaa[16] = { 0xfedcba9876543210,0xedcba9876543210f,0xdcba9876543210fe,0xcba9876543210fed , 0xba9876543210fedc,0xa9876543210fedcb,0x9876543210fedcba,0x876543210fedcba9 , 0x76543210fedcba98,0x6543210fedcba987,0x543210fedcba9876,0x43210fedcba98765 , 0x3210fedcba987654,0x210fedcba9876543,0x10fedcba98765432,0x0fedcba987654321 }; unsigned iii; for (iii=0; iii < 16; iii++) { val = swap64 (aaaa[iii]); printf("A[]=%016llX Sw=%016llx\n", aaaa[iii], val); } return 0; } 

I thought this is one of the simplest way to reverse the bit. please let me know if there is any flaw in this logic. basically in this logic, we check the value of the bit in position. set the bit if value is 1 on reversed position.

 void bit_reverse(ui32 *data) { ui32 temp = 0; ui32 i, bit_len; { for(i = 0, bit_len = 31; i <= bit_len; i++) { temp |= (*data & 1 << i)? (1 << bit_len-i) : 0; } *data = temp; } return; } 

Bit reversal in pseudo code

source -> byte to be reversed b00101100 destination -> reversed, also needs to be of unsigned type so sign bit is not propogated down

copy into temp so original is unaffected, also needs to be of unsigned type so that sign bit is not shifted in automaticaly

 bytecopy = b0010110 

LOOP8: //do this 8 times test if bytecopy is < 0 (negative)

  set bit8 (msb) of reversed = reversed | b10000000 else do not set bit8 shift bytecopy left 1 place bytecopy = bytecopy << 1 = b0101100 result shift result right 1 place reversed = reversed >> 1 = b00000000 8 times no then up^ LOOP8 8 times yes then done. 

The Question asked is for reversing a byte (8 Bits of data)

 typedef unsigned char byte; byte reverseByte(byte a) { int i; byte b = 0; for ( i = 0 ; i < 8 ; i ++) { b <<= 1; b |= ( (a & (1 << i)) >> i); } return b; } 
 unsigned char ReverseBits(unsigned char data) { unsigned char k = 0, rev = 0; unsigned char n = data; while(n) { k = n & (~(n - 1)); n &= (n - 1); rev |= (128 / k); } return rev; } 

I think the simplest method I know follows. MSB is input and LSB is 'reversed' output:

 unsigned char rev(char MSB) { unsigned char LSB=0; // for output _FOR(i,0,8) { LSB= LSB << 1; if(MSB&1) LSB = LSB | 1; MSB= MSB >> 1; } return LSB; } // It works by rotating bytes in opposite directions. // Just repeat for each byte. 
 // Purpose: to reverse bits in an unsigned short integer // Input: an unsigned short integer whose bits are to be reversed // Output: an unsigned short integer with the reversed bits of the input one unsigned short ReverseBits( unsigned short a ) { // declare and initialize number of bits in the unsigned short integer const char num_bits = sizeof(a) * CHAR_BIT; // declare and initialize bitset representation of integer a bitset<num_bits> bitset_a(a); // declare and initialize bitset representation of integer b (0000000000000000) bitset<num_bits> bitset_b(0); // declare and initialize bitset representation of mask (0000000000000001) bitset<num_bits> mask(1); for ( char i = 0; i < num_bits; ++i ) { bitset_b = (bitset_b << 1) | bitset_a & mask; bitset_a >>= 1; } return (unsigned short) bitset_b.to_ulong(); } void PrintBits( unsigned short a ) { // declare and initialize bitset representation of a bitset<sizeof(a) * CHAR_BIT> bitset(a); // print out bits cout << bitset << endl; } // Testing the functionality of the code int main () { unsigned short a = 17, b; cout << "Original: "; PrintBits(a); b = ReverseBits( a ); cout << "Reversed: "; PrintBits(b); } // Output: Original: 0000000000010001 Reversed: 1000100000000000 
 This is for 32 bit, we need to change the size if we consider 8 bits. void bitReverse(int num) { int num_reverse = 0; int size = (sizeof(int)*8) -1; int i=0,j=0; for(i=0,j=size;i<=size,j>=0;i++,j--) { if((num >> i)&1) { num_reverse = (num_reverse | (1<<j)); } } printf("\n rev num = %d\n",num_reverse); } 

// reading the input integer "num" in LSB->MSB order and storing in num_reverse in MSB->LSB order.

Another loop-based solution that exits quickly when the number is low (in C++ for multiple types)

 template<class T> T reverse_bits(T in) { T bit = static_cast<T>(1) << (sizeof(T) * 8 - 1); T out; for (out = 0; bit && in; bit >>= 1, in >>= 1) { if (in & 1) { out |= bit; } } return out; } 

or in C for an unsigned int

 unsigned int reverse_bits(unsigned int in) { unsigned int bit = 1u << (sizeof(T) * 8 - 1); unsigned int out; for (out = 0; bit && in; bit >>= 1, in >>= 1) { if (in & 1) out |= bit; } return out; } 

It seems that many other posts are concerned about speed (ie best = fastest). What about simplicity? विचार करें:

 char ReverseBits(char character) { char reversed_character = 0; for (int i = 0; i < 8; i++) { char ith_bit = (c & (1 << i)) >> i; reversed_character |= (ith_bit << (sizeof(char) - 1 - i)); } return reversed_character; } 

and hope that clever compiler will optimise for you.

If you want to reverse a longer list of bits (containing sizeof(char) * n bits), you can use this function to get:

 void ReverseNumber(char* number, int bit_count_in_number) { int bytes_occupied = bit_count_in_number / sizeof(char); // first reverse bytes for (int i = 0; i <= (bytes_occupied / 2); i++) { swap(long_number[i], long_number[n - i]); } // then reverse bits of each individual byte for (int i = 0; i < bytes_occupied; i++) { long_number[i] = ReverseBits(long_number[i]); } } 

This would reverse [10000000, 10101010] into [01010101, 00000001].

My simple solution

 BitReverse(IN) OUT = 0x00; R = 1; // Right mask ...0000.0001 L = 0; // Left mask 1000.0000... L = ~0; L = ~(i >> 1); int size = sizeof(IN) * 4; // bit size while(size--){ if(IN & L) OUT = OUT | R; // start from MSB 1000.xxxx if(IN & R) OUT = OUT | L; // start from LSB xxxx.0001 L = L >> 1; R = R << 1; } return OUT; 
 int bit_reverse(int w, int bits) { int r = 0; for (int i = 0; i < bits; i++) { int bit = (w & (1 << i)) >> i; r |= bit << (bits - i - 1); } return r; } 
 int main() { int n; scanf("%d", &n); while (n) { if (n & 1) printf("1"); else printf("0"); n >>= 1; } printf("\n"); } Output: 25 10011