How to Find Next Higher Number With Same Bits in Golang

The challenge

Find the next higher number (int) with same ‘1’- Bits.

I.e. as much 1 bits as before and output next higher than input. Input is always an int in between 1 and 1«30 (inclusive). No bad cases or special tricks…

Examples:

Input: 129  => Output: 130 (10000001 => 10000010)
Input: 127 => Output: 191 (01111111 => 10111111)
Input: 1 => Output: 2 (01 => 10)
Input: 323423 => Output: 323439 (1001110111101011111 => 1001110111101101111)

The solution in Golang

Option 1:

package solution
func NextHigher(x int) int {
  rightOne := x & -x
  nextHigherOneBit := x + rightOne
  rightOnesPattern := x ^ nextHigherOneBit
  rightOnesPattern = (rightOnesPattern) / rightOne
  rightOnesPattern >>= 2
  next := nextHigherOneBit | rightOnesPattern
  return next
}

Option 2:

package solution
import (
  "strconv"
  "strings"
)
func NextHigher(n int) int {
  for i := n+1 ; i > 0 ; i ++ {
    if strings.Count(strconv.FormatInt(int64(n), 2) , "1") == strings.Count(strconv.FormatInt(int64(i), 2) , "1") { return i } }
  return 0
}

Option 3:

package solution
import (
  "math/bits"
)
func NextHigher(n int) int {
  bcount := bits.OnesCount32(uint32(n))
  for x := uint32(n+1); ;x++ {
    if bits.OnesCount32(x) == bcount {
      return int(x)
    }
  }
  return 0
}

Test cases to validate our solution

package solution_test
import (
  . "github.com/onsi/ginkgo"
  . "github.com/onsi/gomega"
)
var _ = Describe("Kata", func() {
    It("Basic tests", func() {
        Expect(NextHigher(128)).To(Equal(256))
        Expect(NextHigher(1)).To(Equal(2))
        Expect(NextHigher(1022)).To(Equal(1279))
        Expect(NextHigher(127)).To(Equal(191))
        Expect(NextHigher(1253343)).To(Equal(1253359))
    })
})