The folks at Dev 102 posted a programming job interview challenge. It is rather easy, but I figured that it may be a nice change of pace, since my last posting was fairly involved.

The challenge is to reverse the bits in each byte, given a large array of bytes. What is the fastest possible solution?

There are only 256 possible values for an 8-bit integer, so it makes sense to pre-compute the reverse of each ahead of time. Then, we can simply scan through the input, and reverse each byte by a simple array lookup. We pay a small initialization cost, but after that, we can reverse bytes nearly as fast as we can read them.

And how to efficiently reverse a byte? There is an obvious solution which uses a for loop and some bit manipulation. My solution below uses a slightly faster approach. It is a nice trick, and not very difficult, so I will leave the details as an exercise to the reader. ;-)

Here is a simple solution in C#:

// Reverses bits in each byte in the array 
static void Reverse(byte[] bytes) 
{ 
    // Precompute the value of each reversed byte 
    byte[] reversed = new byte[256]; 
    for (int i = 0; i < 256; i++) reversed[i] = Reverse((byte)i);  

    // Reverse each byte in the input 
    for (int i = 0; i < bytes.Length; i++) bytes[i] = reversed[bytes[i]]; 
}  

// Reverses bits in a byte 
static byte Reverse(byte b) 
{ 
    int rev = (b >> 4) | ((b & 0xf) << 4); 
    rev = ((rev & 0xcc) >> 2) | ((rev & 0x33) << 2); 
    rev = ((rev & 0xaa) >> 1) | ((rev & 0x55) << 1);  

    return (byte)rev; 
}

If we are going to be reversing multiple arrays, we can hoist the pre-computation into an initialization routine. And, if handling short arrays is important, we can skip the pre-computation step if the array length is less than 256, and just reverse each byte by calling Reverse(byte).

Not sure what else to add… problem solved!

Tags:

16 Comments to “Programming job interview challenge”

  1. Olivier says:

    “problem solved” … not so sure, maybe you’ve totally failed the test!…

    When I asked such a question about bits to a developer I want to hire, the answer I give to the ones proposing some “bit-slicing code” is : “a good developer is not supposed to answer such a challenge but to concentrate on architecture, specifications and testing” …

    :-)

  2. Olivier: Probably the most important thing to do as an interview candidate is to make sure that you understand the point of each question, so that you don’t spend 5 minutes talking off-topic.

    If the interviewer wants to see whether you understand the software engineering process, don’t start talking about bit tricks. If the interviewer wants to see whether you can code, don’t start talking about architecture, specification and testing.

    So, my posting may or may not be the right answer to an interview question – it depends on what the question is!

    However, from the interviewer side, failing a candidate simply because they misunderstood what you are getting at in your question is probably not a good way to hire the best developers. Of course, if you stop them and clarify the question, but they still insist on talking about something else, then that is a problem.

  3. […] Programming job interview challenge [igoro.com] […]

  4. Duc says:

    Dear Igor,

    Cool stuff and thanks.

    What do you think about the below implementation?

    typedef unsigned char uint8;
    typedef struct ch_bit char_bit;
    struct ch_bit
    {
    uint8 f:1;
    uint8 s:1;
    uint8 t:1;
    uint8 fo:1;
    uint8 ff:1;
    uint8 sx:1;
    uint8 sv:1;
    uint8 e:1;
    } __attribute__ ((__packed__));

    char_bit reverse_array[256];
    char_bit *cbi;
    char_bit *cba;
    uint8 i;
    for (i = 0; i f = cbi->e;
    cba->s = cbi->sv;
    cba->t = cbi->sx;
    cba->fo = cbi->ff;
    cba->ff = cbi->fo;
    cba->sx = cbi->t;
    cba->sv = cbi->s;
    cba->e = cbi->f;
    }
    printf (“I am done :-), :-), :-)”);

    This is not cool as yours. But implementation-wise it is
    much simpler; speed-wise I think it is fast too.

    Again, thanks for cool posts.

    Regards
    Duc

  5. Duc says:

    Dear Igor,

    Sorry about the last post; something is missing;
    I am reposting the main body. Sorry again. Thanks
    again.

    =============================================================
    uint16 i;
    for (i = 0; i f = cbi->e;
    cba->s = cbi->sv;
    cba->t = cbi->sx;
    cba->fo = cbi->ff;
    cba->ff = cbi->fo;
    cba->sx = cbi->t;
    cba->sv = cbi->s;
    cba->e = cbi->f;
    }
    printf (“I am done :-), :-), :-)”);

    ========================================================

  6. Duc: Crazy C tricks with packed structs. :)

    Interesting.

  7. Duc says:

    Dear Igor,

    Yes it is interesting crazy :-), :-), :-).
    Also, it is also slower than your version (compiler
    can not compete with handcraft-assembler code).

    Regards
    DL

  8. Philip says:

    There is another interesting approach to inverting bits problem.

    Let us assume you need to reverse each number in range [0 .. 2^n – 1]. Notice that “increment some number” means delete (i.e. change to 0’es) a group of 1’s at the end of it and place 1 before this group. So if you know reversed(m) and want to get reversed(m + 1) then all you need is to delete a group of ones at the beginning of reversed(m) and place 1 right after them.

    Here is the code:

    int MAX = (1 << n);
    for (int i = 0, revi = 0; i > 1);
    for (; revi & bit; bit >>= 1)
    revi ^= bit;
    revi |= bit;

    reversed[i] = revi;
    }

    Careful analysis shows, that this algorithm works in linear time.

  9. Philip says:

    It seems commenting engine ate some parts of C++ code in my last comment.
    Here is the original.

  10. Philip: Yes, that approach certainly works. In fact, that’s the approach I was referring to when I said that “There is an obvious solution which uses a for loop and some bit manipulation”

  11. Jake says:

    Igor & co – as long as you use a pre-cached array, it does not really matter how you init it – fast or slow c trick make no diff.
    The only reason to use bit tricks here is if you can make the reverse function faster than the array lookup. The array lookup is very cheap so unbeatable.

    If array lookup is “free”, I’d expect a “good” answer to at least mention that you can use 64kb array. How about a 4gb array?

    What about cache misses? this could cost you 200 cycles per 64 bytes. So it might be worthwhile to skip the array for an input shorter than, say, 100 cycles to process, for the 256 byte array. Probably a lot more for bigger ones (which renders it a good answer only in theory). Micro benchmarks will not give you the answer in this case, only real life probing.

  12. Jake says:

    Sorry, I forgot to mention what was obvious to me – 64kb array you use to reverse 2 bytes at a time.

  13. Matthew Davidson says:

    Here’s a question for the low-level guys here: If you needed to reverse the bits of larger data sizes (e.g. 32-bit words), how does taking advantage of two’s complement representation compare to bit-shifting? That is, for any signed word, you could simply multiply by -1 and then subtract 1, to flip all the bits.

    Even more relevant to the array example, what would it cost (relative to a byte-focused solution) to cast the bytes into something larger (32/64-bit), and then flip the larger-sized chunks, rather than doing array lookup of preflipped bytes?

  14. Anon says:

    Why is this article not in the 2008 archive list?

  15. Anon says:

    @Matthew:

    Your method would not be a solution to the proposed problem.

    For a 4-bit number:

    0001 val = 1
    1111 val = -1 (multiply by -1)
    1110 val = -2 (subtract 1)

    but you want as a result: 1000

  16. Anon says:

    @Philip:

    Your algorithm contains a small flaw, for n=4
    reversed[0] = 8
    reversed[1] = 4

    reversed[15] = 0

    The correct initialization of the outer loop is

    reversed[0] = 0;
    for (int i = 1, revi = 0; .......

Leave a Reply

You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>