这里有一个Java编写的测试用例,用于检查解决方案是否正确。
(它是为我的解决方案编写的,但在某些情况下被证明不正确,因此我删除了该答案,但测试用例仍然相关。)
Matt Timmermans
的答案通过了所有测试用例,包括负数。
而Integer.bitCount(val ^ (3 * val))
通过了大多数测试用例,除了输入为Integer.MAX_VALUE
的情况。
代码
MinCountOf2PowerTest.java
import org.testng.Assert;
import org.testng.annotations.Test;
public class MinCountOf2PowerTest {
@Test
public void testPositive() {
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01010001", 2)), 3);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011", 2)), 2);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0111", 2)), 2);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01111", 2)), 2);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.MAX_VALUE), 2);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01101", 2)), 3);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011011", 2)), 3);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0100000111", 2)), 3);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("010010000000111", 2)), 4);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0100100000001111111", 2)), 4);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("010011000000001111111", 2)), 5);
}
@Test
public void testZero() {
Assert.assertEquals(MinCountOf2Power.minCount(0), 0);
}
@Test
public void testNegative() {
Assert.assertEquals(MinCountOf2Power.minCount(-1), 1);
Assert.assertEquals(MinCountOf2Power.minCount(-9), 2);
Assert.assertEquals(MinCountOf2Power.minCount(-100), 3);
}
@Test
public void testPositiveVsNegative() {
for (int i = 1; i <= 1000; i++) {
Assert.assertEquals(MinCountOf2Power.minCount(i), MinCountOf2Power.minCount(-i));
}
Assert.assertEquals(MinCountOf2Power.minCount(Integer.MAX_VALUE), MinCountOf2Power.minCount(-Integer.MAX_VALUE));
}
@Test
public void testCornerEnding0() {
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01110", 2)), 2);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011110", 2)), 2);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("011100", 2)), 2);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("0111000", 2)), 2);
Assert.assertEquals(MinCountOf2Power.minCount(Integer.parseInt("01110000", 2)), 2);
}
@Test
public void testOpInput() {
Assert.assertEquals(MinCountOf2Power.minCount(15), 2);
Assert.assertEquals(MinCountOf2Power.minCount(8), 1);
Assert.assertEquals(MinCountOf2Power.minCount(0), 0);
}
}
提示:
- 这是用
Java
编写的,使用了TestNG
。
- 但是,只需替换导入语句,您也可以使用
JUnit
。
- 或者通过具有特定语法的输入/输出值对将其翻译为其他语言。
- 我还发现正整数总是与其负数具有相同的结果。
并且还包括一个测试用例来证明这一点。
bitCount
被使用!给定bitCount
和最大位位置,一个替代方案是可以计算 1 和 0 的数量,从而确定是否添加或从下一个更大的 2 的幂开始并减去。例如,33 的最大位为6,bitCount
为2(即4个零),因此由于bitCount
< 零,使用加法。另一方面,30 的最大位为5,bitCount
为4(即1个零),因此由于bitCount
> 零,从32开始使用减法。(当然,我还没有看到bitCount
,因为我没有计算奇偶性) - racramanInteger.parseInt(sb.toString(), 2);
??? 你在制造字符串,然后将它们解析回整数?这似乎比仅对整数进行暴力攻击要慢得多...为什么不使用x&1
和x>>=1
从lsb到msb检查位是否设置...记住位是否连续,然后构造+2^bit
或+2^(maxbit+1) - 2^(minbit)
。 - Spektre