牛顿迭代法、数学定理、二分查找、无符号位移运算。--判断数字N为平方数

118 阅读 0 评论 78 点赞

我是靠谱客的博主愤怒鸵鸟，最近开发中收集的这篇文章主要介绍牛顿迭代法、数学定理、二分查找、无符号位移运算。--判断数字N为平方数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

如何在不使用内置函数库的情况下判断一个数N为完全平方数，即N是可以被开方的数？

题目来自LeetCode网367号题：

这里例举四种方法：

一、暴力破解：

        double i = 1;
        while(i * i < num) i++;
        return i * i == num;

二、数学定理：

很明显，所有能被开方的数都存在这样的一个n，满足 N^2 = 1 + 3 + 5 + 7 + ...+ (2*n - 1)；

         int i = 1;
         while(num > 0) {
             num -= i;
             i += 2;
         }
         return num == 0;

三、二分查找：二分查找不必多说！

        int low = 1;
        int high = num /2;
        int mid = 0;
        while (low <= high){
            mid = (low + high)/2;
            if ((double)mid*mid > num){
                high = mid - 1;
            }else if ((double)mid*mid < num){
                low = mid + 1;
            }else{
                return true;
            }
        }
        return false;

四、牛顿迭代法、关于这个得好好讲讲，设计到一些数学知识。

牛顿迭代法用于快速寻找平方根！

例如，我想求根号2等于多少。假如我猜测的结果为4，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号2了：

( 4 + 2/ 4 ) / 2 = 2.25
( 2.25 + 2/ 2.25 ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..
….

如下图：

这种算法的原理很简单，我们仅仅是不断用(x,f(x))的切线来逼近方程x^2-num=0的根。根号num实际上就是x^2-num=0的一个正实根，这个函数的导数是2x。也就是说，函数上任一点(x,f(x))处的切线斜率是2x。那么，x-f(x)/(2x)就是一个比x更接近的近似值。代入f(x)=x^2-num得到x-(x^2-num)/(2x)，也就是(x+num/x)/2。

        if(1 == num) return true;
             //估计值
        int t = num / 2;
        while((double)t * t > num){
           //更新估计值
            t = (t + num / t) / 2;
        }
        return t * t == num;

拓展：无符号位移 >>> 或 >>>=

无符号右移 >>> 或 >>> =

无符号右移（>>>）跟右移（>>）运算符不一样。

右移不改变数的正负。

对于一个正数，无符号右移不会变成负数(相当于除以1再取整)；但是对于一个负数，无符号右移会将负数变成正数；

public static void main(String[] args) {
		int t = -4;
		System.out.println("无符号位移一位前：t = " + t + "n二进制t = " + Integer.toBinaryString(t));
		t = t>>>1;
		System.out.println("无符号位移一位后：t = " + t + "n二进制t = " + Integer.toBinaryString(t));
		System.out.println("");
		int s = 5;
		System.out.println("无符号位移一位前：s = " + s + "n二进制s = " + Integer.toBinaryString(s));
		s = s>>>1;
		System.out.println("无符号位移一位后：s = " + s + "n二进制s = " + Integer.toBinaryString(s));
	}