<p>I was reading Joel's book where he was suggesting as interview question:</p>

<blockquote>
  <p>Write a program to reverse the "ON" bits in a given byte.</p>
</blockquote>

<p>I only can think of a solution using C. </p>

<p>Asking here so you can show me how to do in a Non C way (if possible)</p>

[{'answer_id': 9752, 'author': 'Lasse V. Karlsen', 'author_id': 267, 'author_profile': 'https://Stackoverflow.com/users/267', 'pm_score': 2, 'selected': False, 'text': "<p>What specifically does that question mean?</p>\n\n<p>Does <em>reverse</em> mean setting 1's to 0's and vice versa?</p>\n\n<p>Or does it mean <em>00001100</em> --> <em>00110000</em> where you reverse their order in the byte? Or perhaps just reversing the part that is from the first 1 to the last 1? ie. <em>00110101</em> --> <em>00101011</em>?</p>\n\n<p>Assuming it means reversing the bit order in the whole byte, here's an x86 assembler version:</p>\n\n<pre><code>; al is input register\n; bl is output register\n\nxor bl, bl      ; clear output\n\n; first bit\nrcl al, 1       ; rotate al through carry\nrcr bl, 1       ; rotate carry into bl\n\n; duplicate above 2-line statements 7 more times for the other bits\n</code></pre>\n\n<p>not the most optimal solution, a table lookup is faster.</p>\n"}, {'answer_id': 9756, 'author': 'Coincoin', 'author_id': 42, 'author_profile': 'https://Stackoverflow.com/users/42', 'pm_score': 2, 'selected': False, 'text': "<p>Reversing the order of bits in C#:</p>\n\n<pre><code>byte ReverseByte(byte b)\n{\n    byte r = 0;\n    for(int i=0; i&lt;8; i++)\n    {\n        int mask = 1 &lt;&lt; i;\n        int bit = (b &amp; mask) &gt;&gt; i;\n        int reversedMask = bit &lt;&lt; (7 - i);\n        r |= (byte)reversedMask;\n    }\n    return r;\n}\n</code></pre>\n\n<p>I'm sure there are more clever ways of doing it but in that precise case, the interview question is meant to determine if you know bitwise operations so I guess this solution would work.</p>\n\n<p>In an interview, the interviewer usually wants to know how you find a solution, what are you problem solving skills, if it's clean or if it's a hack. So don't come up with too much of a clever solution because that will <em>probably</em> mean you found it somewhere on the Internet beforehand. Don't try to fake that you don't know it neither and that you just come up with the answer because you are a genius, this is will be even worst if she figures out since you are basically lying.</p>\n"}, {'answer_id': 9758, 'author': 'GaryF', 'author_id': 1035, 'author_profile': 'https://Stackoverflow.com/users/1035', 'pm_score': 2, 'selected': False, 'text': '<p>The classic <a href="http://graphics.stanford.edu/~seander/bithacks.html" rel="nofollow noreferrer">Bit Hacks</a> page has several (really very clever) ways to do this, but it\'s all in C. Any language derived from C syntax (notably Java) will likely have similar methods. I\'m sure we\'ll get some Haskell versions in this thread ;)</p>\n'}, {'answer_id': 9778, 'author': 'James A. Rosen', 'author_id': 1190, 'author_profile': 'https://Stackoverflow.com/users/1190', 'pm_score': 2, 'selected': False, 'text': "<blockquote>\n  <p><code>byte ReverseByte(byte b)\n  {\n      return b ^ 0xff;\n  }</code></p>\n</blockquote>\n\n<p>That works if <code>^</code> is XOR in your language, but not if it's <code>AND</code>, which it often is.</p>\n"}, {'answer_id': 9907, 'author': 'Jason Day', 'author_id': 737, 'author_profile': 'https://Stackoverflow.com/users/737', 'pm_score': 4, 'selected': False, 'text': '<blockquote>\n  <p>What specifically does that question mean?</p>\n</blockquote>\n\n<p>Good question.  If reversing the "ON" bits means reversing only the bits that are "ON", then you will always get 0, no matter what the input is.  If it means reversing <em>all</em> the bits, i.e. changing all 1s to 0s and all 0s to 1s, which is how I initially read it, then that\'s just a bitwise NOT, or complement.  C-based languages have a complement operator, <code>~</code>, that does this.  For example:</p>\n\n<pre><code>unsigned char b = 102;      /* 0x66, 01100110 */\nunsigned char reverse = ~b; /* 0x99, 10011001 */\n</code></pre>\n'}, {'answer_id': 9929, 'author': 'palmsey', 'author_id': 521, 'author_profile': 'https://Stackoverflow.com/users/521', 'pm_score': 2, 'selected': False, 'text': '<p>If you\'re talking about switching 1\'s to 0\'s and 0\'s to 1\'s, using Ruby:</p>\n\n<pre><code>n = 0b11001100\n~n\n</code></pre>\n\n<p>If you mean reverse the order:</p>\n\n<pre><code>n = 0b11001100\neval("0b" + n.to_s(2).reverse)\n</code></pre>\n\n<p>If you mean counting the on bits, as mentioned by another user:</p>\n\n<pre><code>n = 123\ncount = 0\n0.upto(8) { |i| count = count + n[i] }\n</code></pre>\n\n<p>♥ Ruby</p>\n'}, {'answer_id': 10130, 'author': 'Nick', 'author_id': 1236, 'author_profile': 'https://Stackoverflow.com/users/1236', 'pm_score': 1, 'selected': False, 'text': '<p>I\'m probably misremembering, but I thought that Joel\'s question was about <strong>counting</strong> the "on" bits rather than reversing them.</p>\n'}, {'answer_id': 10561, 'author': 'C. K. Young', 'author_id': 13, 'author_profile': 'https://Stackoverflow.com/users/13', 'pm_score': 0, 'selected': False, 'text': '<p>Since the question asked for a non-C way, here\'s a Scheme implementation, cheerfully plagiarised from <a href="http://people.csail.mit.edu/jaffer/SLIB" rel="nofollow noreferrer">SLIB</a>:</p>\n\n<pre><code>(define (bit-reverse k n)\n  (do ((m (if (negative? n) (lognot n) n) (arithmetic-shift m -1))\n       (k (+ -1 k) (+ -1 k))\n       (rvs 0 (logior (arithmetic-shift rvs 1) (logand 1 m))))\n      ((negative? k) (if (negative? n) (lognot rvs) rvs))))\n\n(define (reverse-bit-field n start end)\n  (define width (- end start))\n  (let ((mask (lognot (ash -1 width))))\n    (define zn (logand mask (arithmetic-shift n (- start))))\n    (logior (arithmetic-shift (bit-reverse width zn) start)\n            (logand (lognot (ash mask start)) n))))\n</code></pre>\n\n<p>Rewritten as C (for people unfamiliar with Scheme), it\'d look something like this (with the understanding that in Scheme, numbers can be arbitrarily big):</p>\n\n<pre><code>int\nbit_reverse(int k, int n)\n{\n    int m = n &lt; 0 ? ~n : n;\n    int rvs = 0;\n    while (--k &gt;= 0) {\n        rvs = (rvs &lt;&lt; 1) | (m &amp; 1);\n        m &gt;&gt;= 1;\n    }\n    return n &lt; 0 ? ~rvs : rvs;\n}\n\nint\nreverse_bit_field(int n, int start, int end)\n{\n    int width = end - start;\n    int mask = ~(-1 &lt;&lt; width);\n    int zn = mask &amp; (n &gt;&gt; start);\n    return (bit_reverse(width, zn) &lt;&lt; start) | (~(mask &lt;&lt; start) &amp; n);\n}\n</code></pre>\n'}, {'answer_id': 10563, 'author': 'C. K. Young', 'author_id': 13, 'author_profile': 'https://Stackoverflow.com/users/13', 'pm_score': 2, 'selected': False, 'text': '<p>And here\'s a version directly cut and pasted from <a href="http://openjdk.java.net/" rel="nofollow noreferrer">OpenJDK</a>, which is interesting because it involves no loop. On the other hand, unlike the Scheme version I posted, this version only works for 32-bit and 64-bit numbers. :-)</p>\n\n<p>32-bit version:</p>\n\n<pre><code>public static int reverse(int i) {\n    // HD, Figure 7-1\n    i = (i &amp; 0x55555555) &lt;&lt; 1 | (i &gt;&gt;&gt; 1) &amp; 0x55555555;\n    i = (i &amp; 0x33333333) &lt;&lt; 2 | (i &gt;&gt;&gt; 2) &amp; 0x33333333;\n    i = (i &amp; 0x0f0f0f0f) &lt;&lt; 4 | (i &gt;&gt;&gt; 4) &amp; 0x0f0f0f0f;\n    i = (i &lt;&lt; 24) | ((i &amp; 0xff00) &lt;&lt; 8) |\n        ((i &gt;&gt;&gt; 8) &amp; 0xff00) | (i &gt;&gt;&gt; 24);\n    return i;\n}\n</code></pre>\n\n<p>64-bit version:</p>\n\n<pre><code>public static long reverse(long i) {\n    // HD, Figure 7-1\n    i = (i &amp; 0x5555555555555555L) &lt;&lt; 1 | (i &gt;&gt;&gt; 1) &amp; 0x5555555555555555L;\n    i = (i &amp; 0x3333333333333333L) &lt;&lt; 2 | (i &gt;&gt;&gt; 2) &amp; 0x3333333333333333L;\n    i = (i &amp; 0x0f0f0f0f0f0f0f0fL) &lt;&lt; 4 | (i &gt;&gt;&gt; 4) &amp; 0x0f0f0f0f0f0f0f0fL;\n    i = (i &amp; 0x00ff00ff00ff00ffL) &lt;&lt; 8 | (i &gt;&gt;&gt; 8) &amp; 0x00ff00ff00ff00ffL;\n    i = (i &lt;&lt; 48) | ((i &amp; 0xffff0000L) &lt;&lt; 16) |\n        ((i &gt;&gt;&gt; 16) &amp; 0xffff0000L) | (i &gt;&gt;&gt; 48);\n    return i;\n}\n</code></pre>\n'}, {'answer_id': 11412, 'author': 'andrewrk', 'author_id': 432, 'author_profile': 'https://Stackoverflow.com/users/432', 'pm_score': 2, 'selected': False, 'text': '<blockquote>\n  <p>I\'m probably misremembering, but I\n  thought that Joel\'s question was about\n  counting the "on" bits rather than\n  reversing them.</p>\n</blockquote>\n\n<p>Here you go:</p>\n\n<pre><code>#include &lt;stdio.h&gt;\n\nint countBits(unsigned char byte);\n\nint main(){\n  FILE* out = fopen( "bitcount.c" ,"w");\n\n  int i;\n  fprintf(out, "#include &lt;stdio.h&gt;\\n#include &lt;stdlib.h&gt;\\n#include &lt;time.h&gt;\\n\\n");\n\n  fprintf(out, "int bitcount[256] = {");\n  for(i=0;i&lt;256;i++){\n    fprintf(out, "%i", countBits((unsigned char)i));\n    if( i &lt; 255 ) fprintf(out, ", ");\n  }\n  fprintf(out, "};\\n\\n");\n\n  fprintf(out, "int main(){\\n");\n\n  fprintf(out, "srand ( time(NULL) );\\n");\n  fprintf(out, "\\tint num = rand() %% 256;\\n");\n  fprintf(out, "\\tprintf(\\"The byte %%i has %%i bits set to ON.\\\\n\\", num, bitcount[num]);\\n");\n\n  fprintf(out, "\\treturn 0;\\n");\n  fprintf(out, "}\\n");\n  fclose(out);\n\n  return 0;\n}\n\nint countBits(unsigned char byte){\n  unsigned char mask = 1;\n  int count = 0;\n  while(mask){\n    if( mask&amp;byte ) count++;\n    mask &lt;&lt;= 1;\n  }\n  return count;\n}\n</code></pre>\n'}, {'answer_id': 124792, 'author': 'ja.', 'author_id': 15467, 'author_profile': 'https://Stackoverflow.com/users/15467', 'pm_score': 1, 'selected': False, 'text': '<p>Here\'s the obligatory Haskell soln for complementing the bits, it uses the library function, complement:</p>\n\n<pre><code>import Data.Bits\nimport Data.Int\n\ni = 123::Int\ni32 = 123::Int32\ni64 = 123::Int64\nvar2 = 123::Integer\n\ntest1 = sho i\ntest2 = sho i32\ntest3 = sho i64\ntest4 = sho var2 -- Exception\n\nsho i = putStrLn $ showBits i ++ "\\n" ++ (showBits $complement i)\nshowBits  v = concatMap f (showBits2 v) where\n   f False = "0"\n   f True  = "1"\nshowBits2 v = map (testBit v) [0..(bitSize v - 1)]\n</code></pre>\n'}, {'answer_id': 1282737, 'author': 'Brad Ackerman', 'author_id': 113222, 'author_profile': 'https://Stackoverflow.com/users/113222', 'pm_score': 1, 'selected': False, 'text': "<p>I'd modify palmsey's second example, eliminating a bug and eliminating the <code>eval</code>:</p>\n\n<pre><code>n = 0b11001100\nn.to_s(2).rjust(8, '0').reverse.to_i(2)\n</code></pre>\n\n<p>The <code>rjust</code> is important if the number to be bitwise-reversed is a fixed-length bit field -- without it, the reverse of <code>0b00101010</code> would be <code>0b10101</code> rather than the correct <code>0b01010100</code>.  (Obviously, the 8 should be replaced with the length in question.)  I just got tripped up by this one.</p>\n"}, {'answer_id': 1282817, 'author': 'Jason', 'author_id': 100902, 'author_profile': 'https://Stackoverflow.com/users/100902', 'pm_score': 1, 'selected': False, 'text': "<p>If the question means to flip all the bits, and you aren't allowed to use C-like operators such as XOR and NOT, then this will work:</p>\n\n<pre><code>bFlipped = -1 - bInput;\n</code></pre>\n"}, {'answer_id': 1282858, 'author': 'GManNickG', 'author_id': 87234, 'author_profile': 'https://Stackoverflow.com/users/87234', 'pm_score': 4, 'selected': False, 'text': '<p>I claim trick question. :) Reversing all bits means a flip-flop, but only the bits that are on clearly means:</p>\n\n<pre><code>return 0;\n</code></pre>\n'}, {'answer_id': 1282893, 'author': 'tsilb', 'author_id': 11112, 'author_profile': 'https://Stackoverflow.com/users/11112', 'pm_score': 2, 'selected': False, 'text': '<p>pseudo code..</p>\n\n<pre><code>while (Read())\n  Write(0);\n</code></pre>\n'}, {'answer_id': 1282970, 'author': 'Matthew Iselin', 'author_id': 118364, 'author_profile': 'https://Stackoverflow.com/users/118364', 'pm_score': 1, 'selected': False, 'text': '<blockquote>\n  <p>Asking here so you can show me how to do in a <strong>Non C way</strong> (if possible)</p>\n</blockquote>\n\n<p>Say you have the number 10101010. To change 1s to 0s (and vice versa) you just use XOR:</p>\n\n<pre><code> 10101010\n^11111111\n --------\n 01010101\n</code></pre>\n\n<p>Doing it by hand is about as "Non C" as you\'ll get.</p>\n\n<p>However from the wording of the question it really sounds like it\'s <em>only</em> turning off "ON" bits... In which case the answer is zero (as has already been mentioned) (unless of course the question is actually asking to swap the order of the bits).</p>\n'}, {'answer_id': 17915867, 'author': 'Vineet Setia', 'author_id': 2613413, 'author_profile': 'https://Stackoverflow.com/users/2613413', 'pm_score': 0, 'selected': False, 'text': '<p>Reversing the bits.\nFor example we have a number represented by 01101011 . Now if we reverse the bits then this number will become 11010110. Now to achieve this you should first know how to do swap two bits in a number.\nSwapping two bits in a  number:-\nXOR both the bits with one and see if results are different. If they are not then both the bits are same otherwise XOR both the bits with XOR and save it in its original number;\nNow for reversing the number \nFOR I less than Numberofbits/2\n   swap(Number,I,NumberOfBits-1-I);</p>\n'}]
['https://Stackoverflow.com/questions/9750', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/123/']