Day 29 Bitwise AND Operators in C Hackerrank Solution

Day 29 Bitwise AND Operators in C Hackerrank Solution. Day 29: Bitwise AND is the Hackerrank competitive website programming challenge. In this programming challenge, we have to find the maximum possible value of A&B that is also < (K=2 ).

Bitwise AND Operators in C Hackerrank Solution are very easy and simple. Visit the hackerrank website and choose your language C and make your you have clear a coding dashboard now copy the following code and paste it into the editor dashboard and Run the program. After successfully Running submit the code.

Task: Bitwise AND Operators

Given set S = {1, 2, 3, . . . . , N}. Find two integers, A and B (where A<B), from set S such that the value of A&B is the maximum possible and also less than a given integer, K. In this case, & represents the bitwise AND operator.

Basic Operators

Here are some commonly used Java operators you should familiarize yourself with & Bitwise AND (^). This binary operation evaluates to 1 (true) if both operands are true, otherwise 0 (false). In other words:

& Bitwise

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

| Bitwise Inclusive OR

| Bitwise Inclusive OR (V). This binary operation evaluates to 1 if either operand is true, otherwise 0 (false) if both operands are false. In other words:

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

^ Bitwise Exclusive OR

^ Bitwise Exclusive OR or XOR (⊕). This binary operation evaluates to 1 (true) if and only if exactly one of the two operands is 1; if both operands are 1 or 0, it evaluates to 0 (false). In other words:

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

~ Bitwise Unary

~ The unary Bitwise Complement operator flips every bit; for example, the bitwise-inverted 8-bit binary number 01111001 becomes 10000110, and the bitwise-inverted signed decimal integer 8 becomes -9.

Submit Your Solution Here: Click Here

Day 29 Bitwise AND Operators in C Hackerrank Solution

#include <assert.h>

#include <limits.h>

#include <math.h>

#include <stdbool.h>

#include <stddef.h>

#include <stdint.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int main() {
  int T, n, k, i, j, val;
  scanf("%d", & T);
  while (T > 0) {
    int maximum = 0;
    scanf("%d%d", & n, & k);
    int max_val = 0;
    int a = 0, b = k - 1;

    for (a = n; a > 2; a--) {
      if (a == b)
        continue;
      if ((a & b) > max_val) {
        max_val = a & b;
      }
    }

    printf("%d\n", max_val);

    T--;
  }
  return 0;
}

Explanation of Bitwise AND Operators

The explanation of this programming challenge is below please find out and read all the steps carefully.

STEP 1 to Bitwise Operators in C Hackerrank Solution

Since K-1 is the highest possible answer, we will take it as one of the 2 numbers. The other number should be > K-1 due to the AND property and it would be >= K. It’s best to take a number whose binary equivalent is similar to K-1’s binary value. So K would be the best choice.

Note: By doing an OR operation between 2 numbers, the answer would be >= HIGHEST NUMBER of the 2 numbers.

STEP 2: Bitwise Operators in C Hackerrank Solution

To find the other number we perform OR operation between the highest possible answer and the immediate larger number to it.

i.e [(K-1) OR (K-1)+1] which is nothing but [(K-1) OR K] and its result would be >= K.

STEP 3 to Bitwise Operators Hackerrank Solution in C

Now we got the AND pair which are K-1 and K (the minimum possible result of the above OR operation) and our AND result would be <= K-1.

For most cases we will get the final answer as K-1 itself but not for all cases. When K is odd, the final answer will definitely be K-1 because if K is odd, K-1 will be even. Here only the LSB of the binary equivalent will be different. Eg: K=5(0101); K-1=4(0100)
When K is even, K-1 will be odd and both numbers' binary values might not be similar. Eg: K=8(1000); K-1=7(0111).

K-1 will be the answer only when the result of the OR operation is <= N. If it's> N, we would end up using a number which is not in the given number set for the AND operation which might result in a wrong final answer.

So these cases occur when {(K-1 OR K) > N} and when K is even.

For these scenarios, the highest possible answer would not be K-1 and it'll be the next lesser number K-2. The AND pairs for such scenarios would be K-2 and K-1 resulting in a final answer of K-2.

For the above cases, K-1 cannot be the highest possible answer, so we take the lesser number K-2 as the highest possible answer and start again from STEP 1 replacing K-1 with K-2 and K with K-1.

First Scenario

N=5, K=2 ; K-1 = 1

0010 2(K)
0001 1(K-1)
-----OR----
0011 3(OR result)

3 < N

0011 3(OR result)
0001 1(K-1)
-----AND----
0001 1(final answer)

Second Scenario

2.N=8, K=5 ; K-1 = 4

0101 5(K)
0100 4(K-1)
-----OR----
0101 5(OR result)

5 < N

0101 5(OR result)
0100 4(K-1)
-----AND----
0100 4(final answer)

Third Scenario

3.N=2, K=2 ; K-1 = 1 ; K-2 = 0

0010 2(K)
0001 1(K-1)
-----OR----
0011 3(OR result)

3 > N

0001 1(K-1)
0000 0(K-2)
-----OR----
0001 1(OR result)

0001 1(OR result)
0000 0(K-2)
-----AND----
0000 0(final answer)

Fourth Scenario

4.N=21, K=20 ; K-1 = 19 ; K-2 = 18

10100 20(K)
10011 19(K-1)
-----OR----
10111 23(OR result)

23 > N

10011 19(K-1)
10010 18(K-2)
-----OR----
10011 19(OR result)

10011 19(OR result)
10010 18(K-2)
-----AND----
10010 18(final answer)

The above explanation by rospvar. All the credit goes to Rospvar. Thank you for the detailed explanation.

Bitwise AND Operators

As we can see above in Bitwise(Bitwise Operators Hackerrank Solution in C) AND if 1 and 1 then the only condition is true. In this problem, we are taking two inputs from the user first one in number N and the second in K. Now we have to find all sets of numbers S = {1, 2, 3, . . . . , N}. Let's take an example and try to understand the problem "Bitwise AND" easily. suppose N=5 and K=2 then set S={1, 2, 3, 4, 5}. then the combination is below.

1. A = 1, B = 2; A & B = 0
2. A = 1, B = 3; A & B = 1
3. A = 1, B = 4; A & B = 0
4. A = 1, B = 5; A & B = 1
5. A = 2, B = 3; A & B = 2
6. A = 2, B = 4; A & B = 0
7. A = 2, B = 5; A & B = 0
8. A = 3, B = 4; A & B = 0
9. A = 4, B = 5; A & B = 1
10. A = 4, B = 5; A & B = 4

The maximum possible value of A & B (LINE NUMBER 5) that is also < (K = 2) is 1, so we print 1 on a new line. We continue to check A & B value is maximum and A & B value is less than or equal to the K.