首页 > 试题广场 >

牛牛打响指

[编程题]牛牛打响指

热度指数：929 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛在地上捡到了一个手套，他带上手套发现眼前出现了很多个小人，当他打一下响指，这些小人的数量就会发生以下变化：如果小人原本的数量是偶数那么数量就会变成一半，如果小人原本的数量是奇数那么数量就会加一。现在牛牛想考考你，他要打多少次响指，才能让小人的数量变成1。

输入描述:

每个输入包含一个测试用例。
输入的第一行包括一个正整数，表示一开始小人的数量N(1<=N<=10^100)。

输出描述:

对于每个用例，在单独的一行中输出牛牛需要打多少次响指才能让小人的数量变成1。

示例1

输入

输出

算法知识视频讲解

查看答案及解析

Java

luckyxue

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        BigInteger bi = new BigInteger(sc.nextLine());
//        int count = 0;
//        BigInteger two = new BigInteger("2");
//        while (!bi.equals(BigInteger.ONE)) {
//            if (bi.remainder(two).equals(BigInteger.ZERO)) {
//                bi = bi.divide(two);
//            } else {
//                bi = bi.add(BigInteger.ONE);
//            }
//            count++;
//        }
//        System.out.println(count);
//    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            String bin = new BigInteger(str).toString(2);
            int len = bin.length();
            int count = 0;
            for (int i = len - 1; i >= 0; i--) {
                if (bin.charAt(i) == '1') {
                    for (int j = 0; j < i; j++) {
                        if (bin.charAt(j) == '0') {
                            count++;
                        }
                    }
                    break;
                }
            }
            if (bin.length() == 1) {
                System.out.println(0);
            } else {
                System.out.println(len + count + 1);
            }
        }
    }
}

发表于 2018-06-06 19:54:42 回复(1)