Reverse bit positions without toBinaryString

Question

I have been trying to use scala to reverse bit positions by only using shifting, forcing and toggling. I was wondering if somebody could find my error, I have been staring my code too long now :)

Examples:

1010 1010 -> 0101 0101
1100 1001 -> 1001 0011

Here is my code atm:

def reverse(word: Byte): Byte = {
  var r = 0x00                      // Reversed bitstring                          
  for (i <- 0 to 7) {
    if ((word >> (7 - i) & 1) == 1) r = r & 1
    r >> 1
  }
  r
}

Old:

def reverse(word: Byte) = {
    var reversed = 0xFF.toByte  

    for (i <- 0 to 7) {
      if ((word >> i & 1) == 1) {
        reversed = reversed >> 1 
      }
      else reversed = reversed >>> 1
    }
    reversed
}

you do know that you mis-spelled `reverced` in the return, right? — sfletche, Feb 26 '16 at 12:26
Oh, yeah I do. It is just a typo when copying that here. I fixed it now — Duzzz, Feb 26 '16 at 12:28
Your code doesn't compile, for a start. Are you asking how to make it compile, or to fix a wrong answer it produces? Also, you're relying on >> 1-filling, but after the first bit in word (which will cause a zero--filling >>>), the top bit will be zero and so all future shifts (whether >> or >>>) will result in a zero bit. It's a bizarre way of doing it, to be honest, I'm not sure what your intent was... — The Archetypal Paul, Feb 26 '16 at 14:01

0__ · Answer 1 · 2016-02-26T12:51:09.557

Just take any answer for a Java implementation and do it simpler in Scala. (I added an explicit bit-size). Like:

import annotation.tailrec

@tailrec
def reverse(in: Int, n: Int = 8, out: Int = 0): Int =
  if (n == 0) out
  else reverse(in >>> 1, n - 1, (out << 1) | (in & 1))

For the number of bits, copy lowest bit from input to output and shift in opposite directions. Verify:

assert(reverse(0xAA) == 0x55)
assert(reverse(0xC9) == 0x93)
for (x <- 0x00 to 0xFF) assert(reverse(reverse(x)) == x)

score 0 · Answer 2 · answered Feb 26 '16 at 14:17

0

This is a weird problem to spend time solving ... Homework?

 @tailrec
 def reverse(in: Int, out: Int = 0, n: Int = 0): Int = 
  if(in == 0) out else reverse(in >> 1, out | (in & 1) << (7-n), n+1)

answered Feb 26 '16 at 14:17

Dima

39,570
6
44
70

What's with the `out |`? – Det Mar 04 '18 at 12:43

score 0 · Answer 3 · answered Feb 26 '16 at 15:27

java.lang.Integer and Long have methods for reversing of bits (and bytes), but for some silly reason, java.lang.Byte doesnt, so if you were to just use this method, remember to shift over the bytes properly:

Eg: (Integer.reverse(x) >>> 24) & 0xFF

This may be easier than writing all the bitwise operations yourself if not quite up to that, and Oracle implements it with a well optimized version for 32&64 bit integers

Reverse bit positions without toBinaryString

3 Answers3