C: Bitwise Arithmetic in CS50 Week 4

Impact-Site-Verification: 23a12350-4048-4728-8db4-0f3bac3dda32

I came into a term called bitwise arithmetic in CS50 week 4 recover walkthrough video by Brian. I do not understand the reason why he use (buffer[3] & 0xf0) == 0xe0.

After Googling for a while, I try to explain in my own way. The proper term is known as bitwise masking.


1. Our target:

  • (buffer[3] = 0xe0 || 0xe1 || 0xe2 || 0xe3 || 0xe4 … 0xef) == TRUE
  • Above statement is too long, we try to make it shorter.
  • Brian propose : (buffer[3] & 0xf0) == 0xe0
  • Its short

2. Method of “&”:

The “&” in the statement is known as “bitwise AND”. It simply means:

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

3. Testing:

(buffer[3] & 0xf0) == 0xe0

Simply means: (0xe0 || 0xe1 || 0xe2 || 0xe3 || 0xe4 … 0xef & 0xf0) == 0xe0.

We always compare (0xe0 || 0xe1 || 0xe2 || 0xe3 || 0xe4 … 0xef) with 0xf0


Example 1: ((0xe0 & 0xf0) == 0xe0) = TRUE

1110 0000 (Buffer[3] – 0xe0)

1111 0000 (Compare – 0xf0)

1110 0000 (Result – 0xe0 (TRUE))


Example 2: ((0xef & 0xf0) == 0xe0) = TRUE

1110 0000 (Buffer[3] – 0xe0)

1111 0000 (Compare – 0xf0)

1110 0000 (Result – 0xe0 (TRUE))


Example 3: ((0xff & 0xf0) == 0xe0) = FALSE

1111 1111 (Buffer[3] – 0xff )

1111 0000 (Compare – 0xf0)

1111 0000 (Result – 0xf0 (FALSE))


Observations:

  • 0xe “0 ~ f” AND with 0xf0, it will always be “0” or 0000. This is know as bitwise masking. 0xf0 is the mask which make sure “0~f” is always “0”.

4. Why do we use 0xf0 as mask instead or 0xe0?

Lets put 0xe0 as mask.


Example 4: ((0xe0 & 0xe0) == 0xe0) = TRUE

1110 0000 (Buffer[3] – 0xe0)

1110 0000 (Compare – 0xe0)

1110 0000 (Result – 0xe0 (TRUE))


Example 5: ((0xef & 0xe0) == 0xe0) = TRUE

1110 0000 (Buffer[3] – 0xe0)

1110 0000 (Compare – 0xe0)

1110 0000 (Result – 0xe0 (TRUE))


Example 6: ((0xff & 0xf0) == 0xe0) = FALSE

1111 1111 (Buffer[3] – 0xff )

1110 0000 (Compare – 0xe0)

1110 0000 (Result – 0xe0 (TRUE)) — THIS IS NOT WHAT WE WANT!!


Observation:

  • (buffer[3] & 0xe0) == 0xe0 unable to filter out 0xff or 0xf “0~f”.
  • It because if we use 0xe0 (111″0″ 0000) as our mask, it will change either
    • 0xe0 (111″0″ 0000) ; 0 & 0 = 0
    • 0xf0 (111″1″ 0000) ; 0 & 1 = 0
      • Into 0xe0 (111″0″ 0000)
      • This is NOT what we want
  • But, if we use 0xf0 (111″1″ 0000) as our mask, it will change
    • 0xf0 (111″1″ 0000) ; 1 & 1 = 1
      • Into 0xf0 (111″1″ 0000)
        • Which is ((0xf”0~f” & 0xf0) == 0xe0) = FALSE
        • This is what we WANT

5. Conclusion:

  • (buffer[3] & 0xf0) == 0xe0 able to filter out if buffer[3] = 0xf “0~f”.
    • We can use it as a shortening method for (buffer[3] = 0xe0 || 0xe1 || 0xe2 || 0xe3 || 0xe4 … 0xef) == TRUE.
  • (buffer[3] & 0xe0) == 0xe0 NOT able to filter out if buffer[3] = 0xf “0~f”.
    • Therefore, it is not able to use in CS50 week 4 recover problem.

It’s a bit complicated but it is understandable.

Below are some reference for further reading: