{"id":26205,"date":"2017-10-26T20:27:58","date_gmt":"2017-10-26T14:57:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26205"},"modified":"2017-10-26T20:27:58","modified_gmt":"2017-10-26T14:57:58","slug":"c-program-reverse-bits-number","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-program-reverse-bits-number\/","title":{"rendered":"C Program to Reverse Bits of a Number"},"content":{"rendered":"<p>Given an unsigned integer, reverse all bits of it and return the number with reversed bits.<\/p>\n<pre>Input : n = 1\r\nOutput : 2147483648  \r\nOn a machine with size of unsigned\r\nbit as 32. Reverse of 0....001 is\r\n100....0.\r\n\r\nInput : n = 2147483648\r\nOutput : 1<\/pre>\n<p><strong>Recommended:<\/strong> <strong>Please solve it on \u201cPRACTICE\u201d first, before moving on to the solution.<\/strong><\/p>\n<p><strong>Method1 \u2013 Simple<\/strong><br \/>\nLoop through all the bits of an integer. If a bit at ith position is set in the i\/p no. then set the bit at (NO_OF_BITS \u2013 1) \u2013 i in o\/p. Where NO_OF_BITS is number of bits present in the given number.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20Function%20to%20reverse%20bits%20of%20num%20*%2F%0Aunsigned%20int%20reverseBits(unsigned%20int%20num)%0A%7B%0A%20%20%20%20unsigned%20int%20%20NO_OF_BITS%20%3D%20sizeof(num)%20*%208%3B%0A%20%20%20%20unsigned%20int%20reverse_num%20%3D%200%2C%20i%2C%20temp%3B%0A%20%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20NO_OF_BITS%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20temp%20%3D%20(num%20%26%20(1%20%3C%3C%20i))%3B%0A%20%20%20%20%20%20%20%20if(temp)%0A%20%20%20%20%20%20%20%20%20%20%20%20reverse_num%20%7C%3D%20(1%20%3C%3C%20((NO_OF_BITS%20-%201)%20-%20i))%3B%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20return%20reverse_num%3B%0A%7D%0A%20%0A%2F*%20Driver%20function%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20unsigned%20int%20x%20%3D%202%3B%20%0A%20%20%20%20printf(%22%25u%22%2C%20reverseBits(x))%3B%0A%20%20%20%20getchar()%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Above program can be optimized by removing the use of variable temp. See below the modified code.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dunsigned%20int%20reverseBits(unsigned%20int%20num)%0A%7B%0A%20%20%20%20unsigned%20int%20%20NO_OF_BITS%20%3D%20sizeof(num)%20*%208%3B%0A%20%20%20%20unsigned%20int%20reverse_num%20%3D%200%3B%0A%20%20%20%20int%20i%3B%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20NO_OF_BITS%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if((num%20%26%20(1%20%3C%3C%20i)))%0A%20%20%20%20%20%20%20%20%20%20%20reverse_num%20%7C%3D%201%20%3C%3C%20((NO_OF_BITS%20-%201)%20-%20i)%3B%20%20%0A%20%20%20%7D%0A%20%20%20%20return%20reverse_num%3B%0A%7D\u201d message=\u201dC \u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Time Complexity:<\/strong> O(log n)<br \/>\n<strong>Space Complexity:<\/strong> O(1)<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Method 2 \u2013 Standard<\/strong><\/p>\n<p>The idea is to keep putting set bits of the num in reverse_num until num becomes zero. After num becomes zero, shift the remaining bits of reverse_num.<\/p>\n<p>Let num is stored using 8 bits and num be 00000110. After the loop you will get reverse_num as 00000011. Now you need to left shift reverse_num 5 more times and you get the exact reverse 01100000.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dunsigned%20int%20reverseBits(unsigned%20int%20num)%0A%7B%0A%20%20%20%20unsigned%20int%20count%20%3D%20sizeof(num)%20*%208%20-%201%3B%0A%20%20%20%20unsigned%20int%20reverse_num%20%3D%20num%3B%0A%20%20%20%20%20%0A%20%20%20%20num%20%3E%3E%3D%201%3B%20%0A%20%20%20%20while(num)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20reverse_num%20%3C%3C%3D%201%3B%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20reverse_num%20%7C%3D%20num%20%26%201%3B%0A%20%20%20%20%20%20%20num%20%3E%3E%3D%201%3B%0A%20%20%20%20%20%20%20count\u2013%3B%0A%20%20%20%20%7D%0A%20%20%20%20reverse_num%20%3C%3C%3D%20count%3B%0A%20%20%20%20return%20reverse_num%3B%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20%20%20unsigned%20int%20x%20%3D%201%3B%0A%20%20%20%20printf(%22%25u%22%2C%20reverseBits(x))%3B%0A%20%20%20%20getchar()%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Time Complexity:<\/strong> O(log n)<br \/>\n<strong>Space Complexity:<\/strong> O(1)<\/p>\n<p><strong>Method 3 \u2013 Lookup Table:<\/strong><br \/>\nWe can reverse the bits of a number in O(1) if we know the size of the number. We can implement it using look up table. Go through the below link for details. You will find some more interesting bit related stuff there..<\/p>\n[ad type=\u201dbanner\u201d]\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>C Program to Reverse Bits of a Number &#8211; Bit Algorithm &#8211; Given an unsigned integer, reverse all bits of it and return the number with reversed bits.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,74852,69866,1],"tags":[75277,75107,77845,75266,75267,75115,75285,75102,75114,75099,75110,75282,75083,75079,75088,75269,75263,75279,75276,75112,75111,75286,75274,71939,75278,75109,75078,77846,75272,75098,75106,75281,75283,75089,77848,76117,71936,77849,77844,75275,77847,75104,75291,77850,75271,75280,75288,75118,75086,75290],"class_list":["post-26205","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-bit-algorithms","category-c-programming","category-coding","tag-2-power-32-value","tag-32-bit-word","tag-binary-mask","tag-binary-operation","tag-binary-operator-in-c","tag-bit-manipulation","tag-bit-manipulation-programs-in-c","tag-bit-number","tag-bit-reversal","tag-bit-table","tag-bitcount","tag-bitwise-logical-operators","tag-bitwise-operations-in-c","tag-bitwise-operator-in-c","tag-bitwise-operator-in-c-example-programs","tag-bitwise-operators","tag-bitwise-operators-in-c","tag-bitwise-operators-in-c-with-examples","tag-bitwise-operators-in-embedded-c","tag-c-bit","tag-c-byte","tag-c-language-bits","tag-c-language-shift-operator","tag-c-program-to-reverse-a-number","tag-c-programming-bits","tag-c-xor","tag-clearbit","tag-flip-bit","tag-flip-c","tag-for-bit","tag-java-binary-operators","tag-magic-bit","tag-masking-in-c","tag-nextbit","tag-number-reverse","tag-operation-in-c","tag-program-to-reverse-a-number-in-c","tag-programs-using-bitwise-operators-in-c","tag-reverse-a-number-in-c","tag-reverse-bit","tag-reverse-n","tag-set-bit","tag-twiddle","tag-unsigned-numbers","tag-xor-0","tag-xor-coding","tag-xor-encryption-c","tag-xor-operation-in-c","tag-xor-operator-in-c","tag-xor-table"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26205","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26205"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26205\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26205"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26205"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26205"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}