去年公司内部比赛，有一道算法题

某神秘的组织每年策划组织一次名叫“墨鱼游戏”的活动。因为你在今年的活动中表现优异，组委会邀请你参与下一届游戏的设计。

设计者计划在明年加入一个“消消消”的关卡，方案如下：

每m个人组成一队
每一队领取一个类似gameboy的掌上游戏机，里面只有一个游戏， 叫“消消消”，目标是要将屏幕上的N个方块消剩1个
m人按任意顺序，每人在游戏机上进行1次且仅1次操作。操作有以下3种选择：a. 加一个方块，b.减一个方块, c. 如果当前方块数是偶数，消掉一半的方块；
经过<=m次的操作，如果目标达成，则该组通过本关。如果目标没有达成，则该组被淘汰（意思你懂的。。。）
为了让该游戏比较激(can)烈(ku)，设计者想把N和m的值调成如下：给定某N值，m是能达成该目标的最小值。

但是设计者不太会撸代码，所以希望作为助手的你，给他设计一个程序，能告诉他不同的N值下（N<=18446744073709551615），m值应该是多少。

这道题明显就是超大数，需要用到BigInteger。 首先介绍 BigInteger方法：

方法简介

获取符号位

signum()

常用数学函数

negate() 取负
abs() 绝对值
pow(int) 求幂
gcd(BigInteger) 最大公约数
min(BigInteger) 最小值
max(BigInteger) 最大值

四则运算与取整求余

add(BigInteger) 加法
subtract(BigInteger) 减法
multiply(BigInteger) 乘法
divide(BigInteger) 除法(取整)
remainder(BigInteger) 求余
divideAndRemainder(BigInteger) 取整和求余 返回的是一个数组

获取基本类型的值

不同于基本数值类型的包装类，此处并不是直接强转的
如果太大intValue 和 longValue 将分别返回低的32位和64位
longValue 和 doubleValue可能会被转换为无穷
intValue()
longValue()
floatValue()
doubleValue()

数值类型的准确值

longValueExact()
intValueExact()
shortValueExact()
byteValueExact()
所谓准确就是不会舍入或者转换，因为他们会进行数据长度的校验
否则将会抛出异常
比如

image.png
image.png

位操作相关

and(BigInteger) 与
or(BigInteger) 或
not() 非
xor(BigInteger) 异或
andNot(BigInteger) 返回其值为 (this & ~val) 的 BigInteger 等效于 and(val.not())
shiftLeft(int) 左移
shiftRight(int) 右移

取模与求余对比

计算过程相同
对于整型数a，b来说，取模运算或者求余运算的方法都是：
求 整数商： c = a/b;
计算模或者余数： r = a - c*b.
求模运算和求余运算在第一步不同:
取余运算在取c的值时，向0 方向舍入;
而取模运算在计算c的值时，向负无穷方向舍入;

因此，求模时结果的符号与b一致，求余时结果的符号与a一致
如果a，b都是正整数的话，求模与求余没有区别

mod(BigInteger)
返回其值为 (this mod m) 的 BigInteger，取模不同于 remainder
BigInteger modPow(BigInteger exponent，BigInteger m)

image.png
BigInteger modInverse(BigInteger m)
image.png

bitCount与bitLength

public int bitCount()
返回此 BigInteger 的二进制补码表示形式中与符号不同的位的数量
特别注意这个方法的含义
不是二进制补码表示形式的 1 位的数量，而是与符号不同的

bitLength
最小的二进制补码表示形式的位数，不包括 符号位
对于正 BigInteger，这等于常规二进制表示形式中的位数 就是去掉符号位占用的长度

valueOf(long)

valueOf(long)
包装一个long为BigInteger
BigInteger的valueOf有缓冲的作用

image.png

equals(Object)

equals(Object)
重写了equals方法
数据相等 才是相等

image.png

toString hashCode CompareTo

public String toString(int radix) 转换为指定基数
toString()
hashCode()
compareTo(BigInteger)
小于、等于或大于 时，返回 -1，0，或 1

素数相关

是否素数
public boolean isProbablePrime(int certainty)
如果此 BigInteger 可能为素数，则返回 true，如果它一定为合数，则返回 false
如果 certainty <= 0，则返回 true

参数：
certainty - 调用方允许的不确定性的度量
如果该调用返回 true，则此 BigInteger 是素数的概率超出 ( 1 - 1/(2的certainty次方) )
此方法的执行时间与此参数的值是成比例的
返回：
如果此 BigInteger 可能为素数，则返回 true，如果它一定为合数，则返回 false
public static BigInteger probablePrime(int bitLength，
Random rnd)
返回有可能是素数的、具有指定长度的正 BigInteger
此方法返回的 BigInteger 是合数的概率不超出 2的-100次方

参数：
bitLength - 返回的 BigInteger 的 bitLength。
rnd - 随机比特源，用这些随机比特选择用来进行质数测试的候选数
nextProbablePrime
public BigInteger nextProbablePrime()
返回大于此 BigInteger 的可能为素数的第一个整数
此方法返回的数是合数的概率不超出 2的-100次方

特殊的"位操作"

estBit(int) 计算 (this & (1<<n)) != 0
setBit(int) 计算 this | (1<<n)
clearBit(int) 计算 this & ~(1<<n)
flipBit(int) 计算 this ^ (1<<n)
getLowestSetBit()
返回此 BigInteger 最右端（最低位）1 比特位的索引
也就是从最右边开始数找到的第一个1
此字节的右端开始到本字节中最右端 1 之间的 0 比特的位数
如果此 BigInteger 不包含1位，则返回 -1
计算 this==0? -1 : log2(this & -this)

toByteArray

public byte[] toByteArray()
BigInteger 内部使用int数组进行数据保存
一个int包含4个byte
BigInteger可以使用byte数组构造
也自然能够分解成byte数组进行保存

解题

这道题核心算法操作 就是3个， 加、减、除2 。其核心就是如何尽快逼近2^N 次方。
如何判断偶数，判断奇数。 可以用除法，也可以看最后一个bit 。BigInteger 封装了很多位操作， 利用位操作效率更高。

• 如果最后一个bit 是0， 就除 2 ， 此时右移一位。
• 如果是奇数， 111， +1 之后 就是1000 ，此后 减半收敛更快
• 如果是奇数 101 -1 就是100 ， 减半收敛更快
• 如果是奇数 011 -1 010 ， 减半收敛更快
• 如果是奇数 001 -1 000 减半收敛更快

所以算法如下：

    public static int getNum1(BigInteger n) {
        int number = 0;
        while (n.bitLength() > 1) {
            if (!n.testBit(0)) {
                n = n.shiftRight(1); 

            } else { 
                if (n.testBit(2) && n.testBit(1) && n.testBit(0)) {
                    n = n.add(BigInteger.valueOf(1l));
                } else {
                    n = n.subtract(BigInteger.valueOf(1l));
                }

            }
            number++;
        }
        return number;
    }