Alternative solution for 5.4

#1

An alternative solution for 5.4 is:

def sameweight(word: Int) = {
  var y = word & ~(word - 1)
  if (y == 1) {
    y = (word + 1) & ~(word)
  }
  val z = y >> 1
  (word ^ y) ^ z
}

The insight here is: Find the least bit. If the least bit is not the last one then swap the first zero with the one next to it.

Let me know what you think about this?

1 Like
#2

Looks great to me. Let’s add safety check - if (word == 0 || ~word == 0) then exception.

0 Likes
#3

I like the bit trick a lot. One thing I worried is the boundary case when y = 1. However, there is one thing worth mentioning is that the bit complexity of this algorithm is better.

0 Likes