One day Colin learned how to represent a number in binary form. For example,
the binary form of $(11){10}$ is $(1011){2}$ , and he was very excited!

Further, Eva taught Colin a well-known binary function $lowbit(x)$ which represents the value of the bit corresponding to the lowest $ 1 $ of $ x $ in binary form.

For example, $lowbit(11)=1$, $lowbit(4) = 4$

Colin thought this function was amazing, so he thought of an interesting problem, and then it comes:

Given a binary form of a number $x(x≤2^{10^5})$ , you need to perform some operations on $ x $.

Each turn you can choose one of the following two operations:

  • $ x+=lowbit(x) $ , which means adding the lowest bit of $x$ to $x$

  • $ x-=lowbit(x) $，which means subtracting the lowest bit of $x$ from $x$

  • Now Colin wants to know, what is the minimum number of operations required to turn $x$ into $0$?

输入

1100101

输出

4

分析

题目大意

  • 使用+ - lowbit(x) ，最少多少次操作把 $x$到$0$

题解代码

如果右边的字符是 ‘0’，说明这是一个独立的 “1”，计数加一；
如果右边的字符也是 ‘1’，说明这是一个连续的 “11”，就将这个连续段的第一个 ‘1’ 改为 ‘0’，并将前面的 ‘1’ 变成 ‘0’，直到遇到一个 ‘0’ 为止，再将最后一个 ‘0’ 变成 ‘1’。然后回退一格继续扫描。

  • 人话就是： 连续的111用 $+lowbit(x)$如果是单独是 0001000 用$-logbit(x)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    // 模拟进位
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder sb = new StringBuilder(scanner.nextLine());
        sb.reverse();
        sb.append("00");
        int cnt = 0, n = sb.length();
        for (int i = 0; i < n; i++) {
            // 如果是1的话
            if (sb.charAt(i) == '1') {
                // 不连续的1处理方法
                // 使用 - lowbit(x)
                if (i == n - 1 || sb.charAt(i + 1) == '0') {
                    cnt++;
                } else {
                    // 如果连续就对其进行设置进位
                    // 就是使用 + lowbit(x)
                    while (i < n - 1 && sb.charAt(i) == '1') {
                        sb.setCharAt(i,'0');
                        i++;
                    }
                    sb.setCharAt(i,'1');
                    i--;
                    cnt++;
                }
            }
            
        }
        System.out.println(cnt);
    }

}