notArefill notArefill - 2 months ago 16
C Question

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

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 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

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.

Comments