In this HackerRank 2’s complement problem solution Understanding, 2’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 1, 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 2’s complement representation for each 32-bit integer in the inclusive range from a to b. How many 1’s would you write down in all?
Problem solution in Python.
#!/bin/python3 import os import sys # # Complete the twosCompliment function below. # def twosCompliment(a, b): # # Write your code here. # count = 0 h1 = a h2 = b + 1 for num in range(32): power = 2 ** num sum_a = (h1 // (power * 2)) * power + max(0, (h1 % (power * 2)) - power) sum_b = (h2 // (power * 2)) * power + max(0, (h2 % (power * 2)) - power) print(num, sum_a, sum_b) count += sum_b - sum_a return count if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') t = int(input()) for t_itr in range(t): ab = input().split() a = int(ab[0]) b = int(ab[1]) result = twosCompliment(a, b) fptr.write(str(result) + 'n') fptr.close()
Problem solution in Java.
import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i = 0; i < n; ++i) { System.out.println(bitsum(sc.nextInt(), sc.nextInt())); } } private static long[] t = new long[32]; static { t[0] = 0; t[1] = 1; int p = 2; for (int i = 2; i < 32; i++) { t[i] = 2*t[i-1] + p; p = p << 1; } } public static long bitsum(int x, int y) { if (y > x && x > 0) { return bitsum(y) - bitsum(x-1); } else if (y >= 0 && x == 0) { return bitsum(y); } else if (y == x) { return Integer.bitCount(y); } else if (x < 0 && y == 0) { return bitsum(x); } else if (x < 0 && x < y && y < 0 ) { return bitsum(x) - bitsum(y+1); } else if (x < 0 && x < y && 0 < y) { return bitsum(x) + bitsum(y); } throw new RuntimeException(x + " " + y); } public static long bitsum(int x) { if (x == 0) return 0; if (x < 0) { if (x == -1) { return 32; } else { long y = -(long)x; return 32 * y - bitsum((int)(y - 1)); } } else { int n = x; int sum = 0; int j = 0; int i = 1; int lsb = n & 1; n = n >>> 1; while (n != 0) { sum += lsb * i; lsb = n & 1; n = n >>> 1; i = i << 1; j++; } long tot = t[j] + 1 + sum + bitsum(sum); return tot; } } }
Problem solution in C++.
#include <cstdio> #include <string> #include <cstring> using namespace std; typedef long long i64; i64 zaigao(i64 a) { return a?(zaigao((a>>1))+(a&1)):0; } i64 gao(int a) { if (a==0) { return 0; } return (a&1)?((a>>1)+(gao(a>>1)<<1)+1):(gao(a-1)+zaigao(a)); } i64 haha(i64 a) { return (a<0)?(-32*a-gao(-1-a)):gao(a); } int main() { int z; i64 x,y; for (scanf("%d",&z);z;--z) { scanf("%Ld%Ld",&x,&y); if (x<0) { printf("%Ldn",(y>=0)?(haha(y)+haha(x)):(haha(x)-haha(y+1))); } else if (x==0) { printf("%Ldn",haha(y)); } else { printf("%Ldn",haha(y)-haha(x-1)); } } return 0; }
Problem solution in C.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> long count_set_bits(long n ){ long count = 0; if(!n) return 0; if ( n < 0) { n*=-1; return(32 - count_set_bits(n-1)); } count = 1; while(n &= (n-1)){ count++; } return count; } long long count_set_to_n(long n){ if(!n) return 0; if(n > 0){ if(n%2) return ( (2*count_set_to_n((n-1)/2)) + ((n+1)/2) ); else return (count_set_bits(n) + count_set_to_n(n-1)); } else{ n*=-1; return 32*n -(count_set_to_n(n-1)); } } long long count_in_range(long a , long b){ if(a*b > 0){ if(llabs(a) > llabs(b)){ //printf("1 %lld 2 %lld 3 %ldn", count_set_to_n(a), count_set_to_n(b), count_set_bits(b) ); return llabs(count_set_to_n(a) - count_set_to_n(b) ) + count_set_bits(b); } else if (llabs(b) > llabs(a)) return llabs(count_set_to_n(b) - count_set_to_n(a) ) + count_set_bits(a); else return count_set_bits(a); } else{ return ( count_set_to_n(a) + count_set_to_n(b)); } } int main() { int N,i; long a,b; scanf("%d", &N); for(i = 0; i < N; i++){ scanf("%ld %ld", &a,&b); printf("%lldn", count_in_range(a,b)); } /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }