2021-05-03: given a non negative integer num, how to avoid circular statements,

2021-05-03： Given a nonnegative integer num, How to avoid circular statements , return >=num, And leave num Current ,2 To the power of .

Fuda answer 2021-05-03：

32 An integer ,N=32.

1. Nonnegative integers use int Express . The time complexity is logN.

The binary form of an integer minus one ,1 All the numbers on the right become 1, Finally add 1 Is the result that needs to be returned .

2. Nonnegative integers use float64 Express . Floating point numbers implicitly use log( Integers ) Result , So the complexity is O(1). This method is a bit sneaky , Because the title is an integer , And here we use float64, It's not an integer , But the idea is strange , Therefore, the .

Floating point numbers = Sign bit + Order code + mantissa . When mantissa is not 0 When , The mantissa becomes 0, Order code +1, This is the memory result of the floating point number to be returned ; When mantissa is 0 When , The current floating-point number is the result to be returned .

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "math"
)

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

//  It is known that n Positive number 
//  Return greater than or equal to , And closest to n Of ,2 Value to the power of 
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)
}

// Find the sign bit according to the floating point number , Order code , mantissa 
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
}

// According to the sign bit , Order code , Mantissa floating point number 
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)
}

The results are as follows ：

picture

***

Zuo Shen java Code