当前位置: 代码迷 >> 综合 >> 【算法题】非负 int 型数据,二进制格式最高位 1 的位置
  详细解决方案

【算法题】非负 int 型数据,二进制格式最高位 1 的位置

热度:6   发布时间:2024-01-30 09:45:07.0

比如对于 6,输出应该是 3(6 的二进制表示是 110);对于 1956,输出应该是 11(1956 的二进制表示是 11110100100)。

1、O(n) 复杂度

func IdxOfHighestOne(value int) int {var res = 0for value != 0 {res++value = value >> 1}return res
}

2、O(logn) 复杂度

func IdxOfHighestOne(value int) int {left := 32right := 1m := 1 << 32 - 1for left > right {mid := (left + right) / 2mask := m << (mid-1) & mv := mask & value >> (mid - 1)if v > 1 {right = mid} else if v == 1 {return mid} else if v == 0 {left = mid}}return 1
}

 

  相关解决方案