int val=0xCAFE Test if at least three of last four bits (LSB) are on

Question

I'm trying to learn C on my own. I came across this exercise and i am studying to understand it. I have read about masking bits and in order to get the last four bits we should do val&0xF.I have read this post as well What is Bit Masking?. The part that i need an explanation is why the possible values are 0x7,0xB,0xD,0xE,0xF. I am studying the answer and i have read various articles. If someone is willing to explain to me this part i would appreciate it.

Answer 1

Because these are all the possible numbers with at least three of the last four bits on. If you write down every binary number from 0 to 15, you will see that these have at least three of the last four bits set:

• 0111 (0x7)
• 1011 (0xB)
• 1101 (0xD)
• 1110 (0xE)
• 1111 (0xF)

Think of it like this: every binary number from 0 to 6 has at most 2 bits set:

• 0 (0)
• 1 (1)
• 10 (2)
• 11 (3)
• 100 (4)
• 101 (5)
• 110 (6)

Thus, none of it matches the rule. From 7 up to 15, we have:

• 111 (7)
• 1000 (8)
• 1001 (9)
• 1010 (10)
• 1011 (11)
• 1100 (12)
• 1101 (13)
• 1110 (14)
• 1111 (15)

From these, only 7, 11, 13, 14 and 15 have three of the last four bits set.

This method is easy to implement:

int chk_last_bits2(unsigned x) {
    return ((x & 0x7) == 0x7) || 
            ((x & 0xB) == 0xB) || 
            ((x & 0xD) == 0xD) || 
            ((x & 0xE) == 0xE) || 
            ((x & 0xF) == 0xF);
}

Note that we have to explicitly test for equality for each case. For example, x & 0xB will return a non-zero value for every number with any of 1011 bits set. This is not what we want, we want all of them to be on, which can be tested with equality.

Another possible solution would be:

int chk_last_bits(unsigned x) {
    int i, j;
    for (i = 1, j = 0; i < 32; i <<= 1)
        if (i & x)
            j++;
    return j >= 3;
}

Since you're learning C, I'll leave this one for you to try to understand.

Answer 2

Masking means filtering bits and keeping only some of them, which are of interest, as you will have understood.

Let's say that you have a variable something and a mask, both are unsigned values: something & mask will return a value whose bits are 0 where the mask is 0 and the value they had in something where the mask is 1. This is the and mask.

To understand why you use those particular values, you have to recall how bitwise operations (&, |...) work in C. When you write a & b, then the corresponding bits of the two variables are orderly combined using the specified logical operator. For instance, if a is 10001010 and b is 00000011, then a & b is 00000010 (orderly, 1 and 0, 0 and 0, 0 and 0, 0 and 0, 1 and 0, 0 and 0, 1 and 1, 0 and 1).

If you understood that, then you can understand what those masks will select. Consider their binary representation:

0x7 --> ...00000111 --> the three LSBs
0xb --> ...00001011 --> the first, second and fourth LSBs
0xd --> ...00001101 --> the first, third and fourth LSBs
0xe --> ...00001110 --> the second, third and fourth LSBs
0xf --> ...00001111 --> the 4 LSBs

This was for and masking, which is for extracting values (refer to the answer you linked). xor and or masking would work similarly, just recall how the logical function behaves.

Answer 3

#include <stdio.h>

int main()
{
    /*
        32 Bit binary: 00000000000000001100101011111110
        Decimal: 51966
    */

    int val = 0xCAFE;

    /*
        Note:
            First it does loop, after that it shifts the bits of `i`,
            so `i` is 1 at the beginning.
            When shifting operator appears always think of bits.

        Step 1
        Decimal: i = 1
        32 Bit binary: 00000000000000000000000000000001

        Step 2
        Decimal: 1 << 1 = 2
        32 Bit binary: 00000000000000000000000000000010

        Step 3
        Decimal: 2 << 1 = 4
        32 Bit binary: 00000000000000000000000000000100

        ... and so on ... 1, 2, 4, 8, 16, 32, stop.

        This indicates 2^n.

        ----------------------------------------------------------------

        Inside the for loop we run the AND operator to find out
        which bits are `on` and which are `off`.

        AND only works if both are true.

        Step 1:
        Last bit

            00000000000000000000000000000001
        AND 00000000000000001100101011111110
            ---------------------------------
            00000000000000000000000000000000

        Decimal: 1
        Second last bit

        Step 2:

            00000000000000000000000000000010
        AND 00000000000000001100101011111110
            ---------------------------------
            00000000000000000000000000000010

        Decimal: 2

        ... and so on ...

        As we can see we gradually check for last 4 bits until
        we reach the 4th loop 2^4 = 32 and the loop stops.

    */

    int i;
    for (i = 1; i < 32; i = i << 1) {

        /* 
            You can simply add a counter over here
            and return the value at the end.
        */
        printf("%d\n", i & val);
    }
}