Cerinta completa

Understanding ‘s complement representation is fundamental to learning about Computer Science. It allows us to write negative numbers in binary. The leftmost digit is used as a sign bit. If it is , we have a negative number and it is represented as the two’s complement of its absolute value. Let’s say you wrote down the ‘s complement representation for each -bit integer in the inclusive range from to . How many ‘s would you write down in all?

For example, using an -bit byte rather than bit integer, the two’s complement of a number can be found by reversing all its bits and adding . The two’s complement representations for a few numbers are shown below: 

        |Number|                Representation in
Number   Binary     Inverse     Two's Complement
-3      00000011    11111100    11111101
-2      00000010    11111101    11111110
-1      00000001    11111110    11111111
 0      00000000                00000000
 1      00000001                00000001
 2      00000010                00000010
 3      00000011                00000011

To write down that range of numbers’ two’s complements in bits, we wrote ‘s. Remember to use bits rather than in your solution. The logic is the same, so the bit representation was chosen to reduce apparent complexity in the example.

Function Description

Complete the twosCompliment function in the editor below. It should return an integer.

twosCompliment has the following parameter(s):
– a: an integer, the range minimum
– b: an integer, the range maximum

Input Format

The first line contains an integer , the number of test cases.

Each of the next lines contains two space-separated integers, and .

Constraints

Output Format

For each test case, print the number of ‘s in the -bit ‘s complement representation for integers in the inclusive range from to on a new line.

Sample Input 0

3
-2 0
-3 4
-1 4

Sample Output 0

63
99
37

Explanation 0

Test case 0
-2 has 31 ones
-1 has 32 ones
0 has 0 ones
31+32+0 = 63
Test case 1
-3 has 31 ones
-2 has 31 ones
-1 has 32 ones
0 has 0 ones
1 has 1 ones
2 has 1 ones
3 has 2 ones
4 has 1 ones
31+31+32+0+1+1+2+1 = 99
Test case 2
-1 has 32 ones
0 has 0 ones
1 has 1 ones
2 has 1 ones
3 has 2 ones
4 has 1 ones
32+0+1+1+2+1 = 37

Sample Input 1

4
-5 0
1 7
-6 -3
3 6

Sample Output 1

155
12
122
7

Explanation 1

Test case 0
-5 has 31 ones
-4 has 30 ones
-3 has 31 ones
-2 has 31 ones
-1 has 32 ones
0 has 0 ones
31+30+31+31+32+0 = 155
Test case 1
1 has 1 ones
2 has 1 ones
3 has 2 ones
4 has 1 ones
5 has 2 ones
6 has 2 ones
7 has 3 ones
1+1+2+1+2+2+3 = 12
Test case 2
-6 has 30 ones
-5 has 31 ones
-4 has 30 ones
-3 has 31 ones
30+31+30+31 = 122
Test case 3
3 has 2 ones
4 has 1 ones
5 has 2 ones
6 has 2 ones
2+1+2+2 = 7

Limbajul de programare folosit: java8

Cod:

//https://www.hackerrank.com/challenges/2s-complement
import java.io.*;

public class Solution {
    private final static byte BITS;
    private final static long[] BIT_COUNT_TO_BIT;
    static {
        BITS = 32;
        BIT_COUNT_TO_BIT = new long[BITS+1];
        BIT_COUNT_TO_BIT[0] = 1;
        for(byte i = 1; i <= BITS; i++){
            BIT_COUNT_TO_BIT[i] = ((BIT_COUNT_TO_BIT[i-1] - 1L) << 1) + (1L << (i-1)) + 1L;
        }
    }
    public static void main(String[] args) throws IOException{
        StringBuffer sb = new StringBuffer();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(short T = Short.parseShort(br.readLine()); T > 0; T--){
            String[] temp = br.readLine().split(" ");
            int A = Integer.parseInt(temp[0]);
            int B = Integer.parseInt(temp[1]);
            long bits = bitCountToNum(B) - bitCountToNum(A) + getHammingWeight(A);
            bits += (A < 0 && B >= 0) ? BIT_COUNT_TO_BIT[BITS] - 1L: 0;
            sb.append(bits + "\n");
        }
        System.out.print(sb);
    }
    //Bit count in number
    private static int getHammingWeight(int n){
        byte count = 0;
        while(n != 0){
            count++;
            n &= n-1;
        }
        return count;
    }
    //Bit count to number, inclusive
    private static long bitCountToNum(int n){
        long count = 0;
        for(byte b = BITS; n != 0;){
            int x = 1 << --b;
            if((n & x) != 0){
                n &= ~x;
                count += BIT_COUNT_TO_BIT[b] + n;
            }
        }
        return count;
    }
}

Scor obtinut: 1.0

Submission ID: 464612997

Link challenge: https://www.hackerrank.com/challenges/2s-complement/problem

2’s complement