x 的平方根

CancerTiN · · 1073 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,

由于返回类型是整数,小数部分将被舍去。

Golang解决:

package main

import "fmt"

func binaryFind(x, l, r int) (t int) {
    m := (l + r + 1) >> 1
    if x < m*m {
        t = binaryFind(x, l, m-1)
    } else if (m+1)*(m+1) < x {
        t = binaryFind(x, m, r)
    } else {
        t = m
        if (m+1)*(m+1) == x {
            t++
        }
    }
    return
}

func mySqrt(x int) int {
    return binaryFind(x, 0, x>>1+1)
}

func main() {
    for _, x := range []int{4, 8, 9, 8192, 6, 2147483647} {
        fmt.Println(x, mySqrt(x))
    }
}

标准输出:

4 2
8 2
9 3
8192 90
6 2
2147483647 46340

这里学到的技巧,对正整型使用移位操作可以完成乘除2的运算,即:

  • x = 8; y = x>>1
  • x = 8; y = x/2

上下两个运算获得y的值是一致的。
记住,左移一位相当于乘以一个2,右移一位相当于地板除一个2,并且只对正整型有效果。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:CancerTiN

查看原文:x 的平方根

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1073 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传