2021-05-03：给定一个非负整数num，如何不用循环语句，

原创

福大大架构师每日一题

修改于 2021-05-04 22:27:38

5440

修改于 2021-05-04 22:27:38

文章被收录于专栏：福大大架构师每日一题

2021-05-03：给定一个非负整数num，如何不用循环语句，返回>=num，并且离num最近的，2的某次方。

福大大答案2021-05-03：

32位整数，N=32。

1.非负整数用int表示。时间复杂度是logN。

整数减一后的二进制形式，1右边的数字全部变成1，最后加1就是需要返回的结果。

2.非负整数用float64表示。浮点数隐含用到了log(整数)的结果，所以复杂度是O(1)。这种方法有点偷奸耍滑了，因为题目里是整数，而这里是用float64，并不是整数，但思路奇特，故采纳了。

浮点数=符号位+阶码+尾数。当尾数不为0的时候，尾数变成0，阶码+1，这就是需要返回的浮点数的内存结果；当尾数为0的时候，当前浮点数就是需要返回的结果。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

func main() {
    for i := 1; i <= 129; i++ {
        fmt.Println(i, tableSizeFor1(i), tableSizeFor2(float64(i)))
    }
}

// 已知n是正数
// 返回大于等于，且最接近n的，2的某次方的值
func tableSizeFor1(n int) int {
    n--
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    return twoSelectOne(n < 0, 1, n+1)
}

func twoSelectOne(condition bool, a int, b int) int {
    if condition {
        return a
    } else {
        return b
    }
}

func tableSizeFor2(a float64) float64 {
    _, exp, frac := fromFloat64(a)
    if frac != 0 {
        exp++
        frac = 0
    }
    return getFloat64(0, exp, frac)
}

//根据浮点数求符号位，阶码，尾数
func fromFloat64(f float64) (uint64, uint64, uint64) {
    u := math.Float64bits(f)
    return u >> 63, u >> 52 & 0b00000111_11111111, u & 0b00000000_00001111_11111111_11111111_11111111_11111111_11111111_11111111
}

//根据符号位，阶码，尾数求浮点数
func getFloat64(s uint64, exp uint64, frac uint64) float64 {
    s = s << 63
    exp = exp & 0b00000111_11111111 << 52
    frac = frac & 0b00000000_00001111_11111111_11111111_11111111_11111111_11111111_11111111
    return math.Float64frombits(s | exp | frac)
}

执行结果如下：