FILL BITS

/*
    *  Consider a new bitwise binary operator that we will denote as x $ y. The result of this operator is that the set bits of x "flood outwards" y bits to both the left and the right. 
    *  More precisely, the i-th bit (the least significant bit is considered to be the 0-th) of x $ y will be 1 if and only if x has any bit whose value is 1 and whose position differs by at most y from i (it can differ in either direction).
    *  
    *  Write a program that given unsigned ints x and y, computes x $ y.
    *  Example Inputs:
    *  8 2
    *  8 4
    *  17 1
    *  Outputs (respectively):
    *  62
    *  255
    *  59
    *  Explanation:
    *  In the first case, 8 is 0000..00001000 in binary. The operation causes the only set bit in the number to spread 2 positions in each direction, with a final result of 111110 (original bit underlined), which is 62 in decimal.
    *  In the second case, we spread the same bit 4 positions in each direction. This results in 4 1s to the left of the original bit's position. All 3 available positions to the right of the original bit's position are filled (a 4th would normally be filled, but we have reached the end of the number). The final number is 11111111, the value of which is 255.
    *  In the third case, 17 is 10001 in binary, and spreading the 1s in each direction by 1 gives 111011, which is 59 in decimal.
    *  
    *  Solution Guidance:
    *  Let k be the bit width (maximum number of bits) of the primitive.
    *  Moderate: O(k*y) time.
    *  Moderate: O(y) time.
    *  Hard: O(log(y)) time.
*/
 
#include <iostream>
using namespace std;
 
int getFillBitsMODERATE(int x,int y)
{
    int mask = x;
    for(int i=1; i<=y; i++)
        mask |= mask<<1 | mask >> 1;
    return mask;
}
 
int getFillBitsHARD(int x, int y)
{
    int mask = x;
    do
    {
        if(y%2)
        {
            mask |= mask<<1 | mask >>1;
            y--;
        }
        y/=2;
        mask |= mask<<y | mask >>y;
    }while(y>0);
    return mask;
}
 
int main()
{
    int x = 8;
    int y = 2;
    int testCases;
    cin>>testCases;
    for(int i=0; i<testCases; i++)
    {
        cout<<"\n\nENTER NUMBERS : ";
        cin>>x>>y;
        cout<<"\nEASY  : "<<getFillBitsMODERATE(x,y);
        cout<<"\nHARD  : "<<getFillBitsHARD(x,y);
    }
}