Solving Josephus problem using bitshift instead of string concatenation-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 {
    return int64(63 - bits.LeadingZeros64(uint64(n)))
}

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

Go playground - https://go.dev/play/p/xdwMNVAvTfL