codeSprint 2的补挑战运行速度太慢 [英] CodeSprint 2's Complement challenge running too slowly
问题描述
在原 InterviewStreet codesprint ，有一个关于计数的补1的个数问题重a和b（含）之间的数字presentations。我能够通过所有的测试案例，使用迭代的精度，但是我只能通过两个正确的时间量。有暗示，提到找到一个递推关系，因此我转而使用递归，但它最终采取的时间相同。因此，任何人都可以找到一个更快的方法比我所提供的code做到这一点？输入文件的第一个数字是在文件中的测试用例。我后code提供了一个示例输入文件。
进口java.util.Scanner中;
公共类解决方案{
公共静态无效的主要（字串[] args）{
扫描仪扫描=新的扫描仪（System.in）;
INT numCases = scanner.nextInt（）;
的for（int i = 0; I＆LT; numCases;我++）{
INT一个= scanner.nextInt（）;
INT B = scanner.nextInt（）;
的System.out.println（计数（A，B））;
}
}
/ **
*返回的a和b（含）之间的人的数目
* /
公共静态诠释计数（INT A，INT B）{
诠释计数= 0;
的for（int i = A; I＆LT; = B;我++）{
如果（ⅰ℃，）
计数+ =（32 - countOnes（（ - 1） - 1，0））;
其他
计数+ = countOnes（ⅰ，0）;
}
返回计数;
}
/ **
*返回的1的数目
* /
公共静态INT countOnes（INT一，诠释计数）{
若（a == 0）
返回计数;
如果（％2 == 0）
回报countOnes（A / 2，计数）;
其他
返回countOnes（（A - 1）/ 2，计算+ 1）;
}
}
输入：
3
-2 0
-3 4
-1 4
输出：
63
99
37
第一步就是更换
公共静态INT countOnes（INT一，诠释计数）{
若（a == 0）
返回计数;
如果（％2 == 0）
回报countOnes（A / 2，计数）;
其他
返回countOnes（（A - 1）/ 2，计算+ 1）;
}
其中再次出现的深度日志<子> 2 一，具有更快的实现中，例如著名的位变换
公共静态INT popCount（INT N）{
//计算在每个位对的设置位
// 11 - ＆GT; 10，10 - ＆GT; 01，0 * - ＆GT; 0 *
N - =（N＆GT;＆GT;→1）及0x55555555;
在每个半字节//计数位
N =（（N＆GT;＆GT;→2）及0x33333333）+（N＆安培; 0x33333333）;
在每个字节//计数位
N =（（N＆GT;→4）及0x0F0F0F0F）+（N＆安培; 0x0F0F0F0F）;
//积聚在最高字节，移数
返程（0x01010101 * N）＆GT;＆GT; 24;
// Java的担保环绕式的，所以我们可以在这里使用int，
//在C，人会需要使用无符号或64-bit类型
//避免未定义行为
}
其中使用四个移位，五按位ANDS，一次减法，两个加法和一次乘法，总共13非常便宜的指令
但是，除非范围是非常小的，可以做的多比计算每个个体数的位更好。
让我们考虑的第一个非负数。从0到2 K -1的数字都达 K 位设置。每个位被设置在这些正好一半，所以总比特数是 K * 2 ^（k-1个）。现在让 2 ^ K＆LT; = A＆LT; 2 ^（K + 1）。位的数量总数 0℃= N＆LT = A 是位的数字之和 0℃= N ＆LT; 2 ^氏/ code>，并在数位 2 ^ K＆LT; = N＆LT = A 。第一个计数，如我们上面看到的， K * 2 ^（K-1）。在第二部分，我们有 A - 2 ^ K + 1 的数字，他们每个人都有2 K 比特集，而忽略了引导位，这些位是相同的，在数字 0℃=正＆其中; =（A - 2 ^ k）的，所以
totalBits（A）= K * 2 ^（K-1）+（A - 2 ^ k + 1）+ totalBits（A - 2 ^ K）
现在为负数。在二进制补码， - （N + 1）=〜N ，所以数字 -a＆LT; = N＆LT; = -1 是号<的补code> 0℃= M＆LT; =（A-1）和组位的号码总数 -a＆LT; = N＆LT; = -1 是 A * 32 - totalBits（A-1）
有关位在一系列总数 A＆LT; = N＆LT; = B ，我们要加上或减去，这取决于范围的两端具有相反或相同的符号
//如果n＆GT; = 0，返回设置位的总数
//数字0℃= K＆其中; =正
如果// N'LT; 0，返回组的总比特为
//在数N＆LT; = K＆LT; = -1
公共静态长totalBits（INT N）{
如果（正℃，）{
长着= - （长）N;
返回（一个* 32 - totalBits（（int）的（A-1）））;
}
如果（N 3;）返回N;
INT LG = 0，掩码= N;
//找到n和它的位置在最高设置位
而（掩模→1）{
++ LG;
面膜＆GT;＆GT; = 1;
}
掩模= 1＆其中;＆其中; LG;
//总比特数为0℃= K＆其中; 2 ^ LG
长总= 1L＆LT;＆LT; LG-1;
总* = LG;
//将2 ^ LG位号码
共有+ = N + 1，面膜;
//添加其他的位数2 ^ LG＆其中; = K＆其中; =正
共有+ = totalBits（正面罩）;
总回报;
}
//返回总集位数字a＆LT; = N＆LT; = B
公共静态长totalBits（INT A，INT B）{
如果（B＆LT;一）抛出新抛出：IllegalArgumentException（无效的范围）;
如果（一个== B）返回popCount（一）;
如果（B == 0）返回totalBits（一）;
如果（b将0）返回totalBits（一） - totalBits（B + 1）;
若（a == 0）返回totalBits（B）;
如果（a取代; 0）返回totalBits（二） - totalBits（A-1）;
//现在A＆LT; 0℃下b
返回totalBits（一）+ totalBits（二）;
}
On the original InterviewStreet Codesprint, there's a question about counting the number of ones in the two's complement representations of the numbers between a and b inclusive. I was able to pass all of the test cases for accuracy using iteration, but I was only able to pass two in the correct amount of time. There was hint that mentioned finding a recurrence relation, so I switched to recursion, but it ended up taking the same amount of time. So can anyone find a faster way to do this than the code I've provided? The first number of the input file is the test cases in the file. I've provided a sample input file after the code.
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int numCases = scanner.nextInt();
for (int i = 0; i < numCases; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
System.out.println(count(a, b));
}
}
/**
* Returns the number of ones between a and b inclusive
*/
public static int count(int a, int b) {
int count = 0;
for (int i = a; i <= b; i++) {
if (i < 0)
count += (32 - countOnes((-i) - 1, 0));
else
count += countOnes(i, 0);
}
return count;
}
/**
* Returns the number of ones in a
*/
public static int countOnes(int a, int count) {
if (a == 0)
return count;
if (a % 2 == 0)
return countOnes(a / 2, count);
else
return countOnes((a - 1) / 2, count + 1);
}
}
Input:
3
-2 0
-3 4
-1 4
Output:
63
99
37
A first step is to replace
public static int countOnes(int a, int count) {
if (a == 0)
return count;
if (a % 2 == 0)
return countOnes(a / 2, count);
else
return countOnes((a - 1) / 2, count + 1);
}
which recurs to a depth of log2 a, with a faster implementation, for example the famous bit-twiddling
public static int popCount(int n) {
// count the set bits in each bit-pair
// 11 -> 10, 10 -> 01, 0* -> 0*
n -= (n >>> 1) & 0x55555555;
// count bits in each nibble
n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
// count bits in each byte
n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
// accumulate the counts in the highest byte and shift
return (0x01010101 * n) >> 24;
// Java guarantees wrap-around, so we can use int here,
// in C, one would need to use unsigned or a 64-bit type
// to avoid undefined behaviour
}
which uses four shifts, five bitwise ands, one subtraction, two additions and one multiplication for a total of thirteen very cheap instructions.
But unless the ranges are very small, one can do much better than counting the bits of each individual number.
Let us consider non-negative numbers first. The numbers from 0 to 2k-1 all have up to k bits set. Every bit is set in exactly half of these, so the total number of bits is k*2^(k-1). Now let 2^k <= a < 2^(k+1). The total number of bits in the numbers 0 <= n <= a is the sum of the bits in the numbers 0 <= n < 2^k and the bits in the numbers 2^k <= n <= a. The first count is, as we saw above, k*2^(k-1). In the second part, we have a - 2^k + 1 numbers, each of them has the 2k-bit set, and ignoring the leading bit, the bits of these are the same as in the numbers 0 <= n <= (a - 2^k), so
totalBits(a) = k*2^(k-1) + (a - 2^k + 1) + totalBits(a - 2^k)
Now for the negative numbers. In twos complement, -(n+1) = ~n, so the numbers -a <= n <= -1 are the complements of the numbers 0 <= m <= (a-1) and the total number of set bits in the numbers -a <= n <= -1 is a*32 - totalBits(a-1).
For the total number of bits in a range a <= n <= b, we have to add or subtract, depending on whether both ends of the range have opposite or the same sign.
// if n >= 0, return the total of set bits for
// the numbers 0 <= k <= n
// if n < 0, return the total of set bits for
// the numbers n <= k <= -1
public static long totalBits(int n){
if (n < 0) {
long a = -(long)n;
return (a*32 - totalBits((int)(a-1)));
}
if (n < 3) return n;
int lg = 0, mask = n;
// find the highest set bit in n and its position
while(mask > 1){
++lg;
mask >>= 1;
}
mask = 1 << lg;
// total bit count for 0 <= k < 2^lg
long total = 1L << lg-1;
total *= lg;
// add number of 2^lg bits
total += n+1-mask;
// add number of other bits for 2^lg <= k <= n
total += totalBits(n-mask);
return total;
}
// return total set bits for the numbers a <= n <= b
public static long totalBits(int a, int b) {
if (b < a) throw new IllegalArgumentException("Invalid range");
if (a == b) return popCount(a);
if (b == 0) return totalBits(a);
if (b < 0) return totalBits(a) - totalBits(b+1);
if (a == 0) return totalBits(b);
if (a > 0) return totalBits(b) - totalBits(a-1);
// Now a < 0 < b
return totalBits(a) + totalBits(b);
}
这篇关于codeSprint 2的补挑战运行速度太慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
