In this HackerRank AND Product problem solution, we have given N pairs of long integers A[i] and B[i] and we need to computer and print the bitwise AND of all-natural numbers in the inclusive range between A[i] and B[i].

HackerRank AND Product problem solution


Problem solution in Python.

def and_product(start, end):
    result = start
    steps = end - start 
    i = 0               
    while (start >> i) > 0:
        # If the number of steps causes the ith bit to flip, then
        # the result of that bit should be 0.
        if lmask(start, i + 1) + steps > lmask(-1, i + 1):
            result = bitmask(result, i)
        i += 1
    return result

def lmask(n, k):
    
    return n & ((1 << k) - 1)

def bitmask(n, k):
    
    return n & ((-1 << (k + 1)) | lmask(-1, k))

def main():
    k = int(input())
    for _ in range(k):
        start, end = input().split()
        print(and_product(int(start), int(end)))

main()


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 size = sc.nextInt();
        for(int ii = 0; ii < size; ii++){
            long start = sc.nextLong();
            long end = sc.nextLong();
            
            long moveFactor = 1;
        while(start != end){
            start >>= 1;
            end >>= 1;
            moveFactor <<= 1;
        }
        System.out.println( start * moveFactor);
       
        }
    }
}


Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    
    int t;
    for(cin >> t;t;t--) {
        unsigned int a, b;
        cin >> a >> b;
        for(int i = 0;i < sizeof(a) * 8;i++) {
            if(a >> i == b >> i){
                cout << (a >> i << i) << endl;
                break;
            }
        }
    }
    
    return 0;
}


Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>

uint32_t msb(uint32_t i);
uint32_t and(uint32_t a, uint32_t b);

uint32_t msb(uint32_t i) {
    i |= i >> 1;
    i |= i >> 2;
    i |= i >> 4;
    i |= i >> 8;
    i |= i >> 16;
    
    return i ^ (i >> 1);
}

uint32_t and(uint32_t a, uint32_t b) {
    uint32_t msb_a = msb(a), msb_b = msb(b), max = 0;
    
    if (msb_a == msb_b) {
        do {
            max |= (msb_a & a);
        } while ((msb_a >>= 1) && (a & msb_a) == (b & msb_a));
    }
    
    return max;
}

int main() {
    int t, i;
    uint32_t a, b;
    
    scanf("%d", &t);
    
    for (i = 0; i < t; ++i) {
        scanf("%u %u", &a, &b);
        printf("%u\n", and(a, b));
    }
    
    return 0;
}