Shift the Most Significant Bit to be the Least Significant Bit-CodePudding

I would like to solve the Josephus Problem by doing an efficient bit shift operation instead of using string concatenation.

I wrote this program to solve the Josephus Problem:

func josephusNumber(n int64) int64 {
    binStr := strconv.FormatInt(n, 2)
    binRes := binStr[1:]   binStr[0:1]
    intRes, _ := strconv.ParseInt(binRes, 2, 64)
    return intRes
}

However, I don't like solving the problem with string concatenation. What is a better way to move the Most Significant Bit and make it the Least Significant Bit in the input int64?

CodePudding user response：

You can implement it per the Wiki reference provided for the problem - https://en.wikipedia.org/wiki/Josephus_problem#Bitwise

func highestOneBit(n int64) int64 {
    var pos int64
    for n>>1 != 0 {
        pos  
        n = n >> 1
    }
    return int64(math.Pow(2, float64(pos)))

}

func josephusNumber(n int64) int64 {
    return ^highestOneBit(n*2) & ((n << 1) | 1)
}

Go playground - https://go.dev/play/p/Ad7e8hIE-wQ