执行运算后将二进制值减小为零的算法 [英] Algorithm to reduce the binary value to zero after performing operations

问题描述

我在在线编码平台上遇到了这个问题:

I encountered this problem on an online coding platform:

字符串S包含值V的二进制表示形式，我们需要计算该值变为零之后的运算次数.有2种操作要执行:

String S contains the binary representation of value V and we need to calculate number of operations after which this value becomes zero. There are 2 operations to perform:

1. 如果V被2除以偶数
2. 如果V为奇数减去1

例如，如果S ="111"，则该函数应返回5.说明:字符串S编码为数字V =7.它需要执行五个操作:

For example if S = "111", the function should return 5. Explanation: String S encodes to number V = 7. It requires five operations:

1. V = 7，这很奇怪:减去1得到6
2. V = 6，它是偶数:除以2得到3
3. V = 3，这很奇怪:减去1得到2
4. V = 2，它是偶数:除以2得到1
5. V = 1，这很奇怪:减去1得到0

对于较小的数字，我的代码工作得很好，但是对于疯狂的数字，我在编码平台上超时，这对我的总体得分产生了影响，因为某些测试案例的得分为零.

My code works perfectly fine for smaller numbers, but for insanely large numbers, I get a timeout on the coding platform and this impacts my overall score as I get zero marks for some test cases.

例如:对于重复值为400的'1'字符串S，该函数应返回799,999

For example: For string S having value '1' repeated 400,000 times, the function should return 799,999

对于这样的输入值，出现超时错误.

For such input values, I get a timeout error.

我的代码:

public class Sol3 {

    private static BigInteger bigIntegerTwo = new BigInteger("2");

    public int solution(String S) {
        BigInteger input = new BigInteger(S, 2);
        return getSteps(input, 0);
    }

    private int getSteps(BigInteger input, int counter) {
        if (input.equals(BigInteger.ZERO)) return counter;  
        counter++;
        if (input.mod(bigIntegerTwo).equals(BigInteger.ZERO)) {
            return getSteps(input.divide(bigIntegerTwo), counter);
        } else {
            return getSteps(input.subtract(BigInteger.ONE), counter);
        }
    }

    public static void main(String[] args) {
        Sol3 s = new Sol3();
        System.out.println(s.solution("011100"));
        System.out.println(s.solution("111"));
        System.out.println(s.solution("1111010101111"));
        System.out.println(s.solution("1"));
    }
}

我的代码有什么错误?还是有一种使用位操作的简单方法?

What is the mistake in my code? Or is there a simple method using bit manipulation?

推荐答案

您不需要转换数字数据类型.只需使用字符串即可.公式是:

You don't need conversion the a numeric data type. Just work with the string. The formula is:

<number of ones> + <number of digits> - <index of left most one> - 1

例如，您的解决方法可能是:

For instance, your solution method could be:

public static int solution(String s) {
    int firstOneAt = s.indexOf("1");
    return firstOneAt == -1 ? 0
         : s.replace("0", "").length() + s.length() - firstOneAt - 1;
}

这个想法是，除法运算实际上是向右移一位数字，最右边的零开始下降.它将数字位数减少1.这也是 only 减少数字位数的方法.因此，您需要输入的位数与数字一样多，但有两个例外:

The idea is that the division operation really is a digit-shift to the right, with the rightmost zero dropping off. It reduces the number of digits by 1. It is also the only way to reduce the number of digits. So you need as many divisions as there are digits in your input, with two exceptions:

• 我们不应计算预先填充的零.
• 当只剩下一位有效数字(一位数字)时，将不需要除法:只需将其减去就可以了.

因此，这意味着我们将需要打折前置的零(或找到第一个1位数的位置)并计算其后的位数，然后减去1以补偿不涉及除法的最终运算

So this means we will need to discount prepadded zeroes (or find the position of the first 1-digit) and count the number of digits from there on, and subtract one to compensate for the final operation which will not involve a division.

最重要的是，我们需要对输入中的任何1位数字进行一次减法运算:所有1位数字或早或晚都会移到最右边的位置，此时必须通过减法来消除它.

On top of that we need one subtraction operation for any 1-digit in the input: all 1-digits will sooner or later get shifted into the right most position at which moment a subtraction is necessary to get rid of it.

这篇关于执行运算后将二进制值减小为零的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！