23

Given n and m unsigned integral types, will the expression 

(n & m) <= m

always be true ?

vonbrand
  • 11,412
  • 8
  • 32
  • 52
Vincent
  • 57,703
  • 61
  • 205
  • 388
  • What's an unsigned integral type? – Behe Feb 02 '14 at 11:07
  • 2
    `std::is_integral::value && std::is_unsigned::value` in C++ (`unsigned char, unsigned short int, unsigned int, unsigned long int, unsigned long long int...`) – Vincent Feb 02 '14 at 11:08
  • Good that the c++ tag was added. – Behe Feb 02 '14 at 11:19
  • 5
    This question applies equally well to C, where integral types have been well defined concept since before standardization. – Dale Hagglund Feb 02 '14 at 11:32
  • 1
    @DaleHagglund: It also applies to abstract mathematics, as long as you recognise what the semantics are (i.e. that `&` is a binary AND, and "unsigned integral type" any contiguous subinterval of Z starting from zero). It is not really language dependant. – Amadan Feb 03 '14 at 01:35
  • And obviously for the same reasons `n|m >= m`. I'm fairly certain there's no operator # such that `n # m >= min(n,m) && n # m <= max(n,m)` for any n,m. – MSalters Feb 03 '14 at 11:11

5 Answers5

39

Yes, it is true.

It should be readily apparent that a necessary condition for y > x is that at least one bit position is set to 1 in y but 0 in x. As & cannot set a bit to 1 if the corresponding operand bits were not already 1, the result cannot be larger than the operands.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
5

Yes, it is always true for unsigned integral data types.

Depending on the value of the mask n, some 1-bits in m may become 0-bits; all bits that are 0 in m will remain 0 in the result. From the point of keeping m as high as possible, the best thing that could happen is that all 1-bits would remain in place, in which case the result would equal m. In all other cases, the result will be less than m.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • doing bitwise and (`&`) on signed integers is an undefined behavior – BЈовић Feb 03 '14 at 07:29
  • 1
    @BЈовић I very much doubt that. If both operands are the same signed integer type, resulting bit pattern is well defined. How that bit pattern is interpreted as a signed value, depends on implementation. But it is not UB. – user694733 Feb 03 '14 at 08:12
  • @user694733 Ok,my mistake. It is implementation defined. (http://stackoverflow.com/q/11644362/476681) – BЈовић Feb 03 '14 at 08:38
5

Let m be m1m2m3m4m5m6m7m8 where mi is a bit.

Now let n be n1n2n3n4n5n6n7n8.

What would be m & n? All bits in m that originally was 0, will stay 0, because 0 & anything is 0. All bits that were 1, will be 1 only of the corresponding bit in n is 1.

Meaning that in the "best" case, the number will be the same, but can never get bigger, since not 1's can be created from 0 & anything.

Let's have an example in order to have a better intuition:

Let m be 11101011.
What are the numbers that are bigger than m? 11111111 (trivial), 11111011, 11101111, 11111010, 11111110.

n1n2n3n4n5n6n7n8
↓  ↓  ↓  ↓  ↓ ↓  ↓ ↓  &
1  1  1  0  1 0  1 1  
-----------------------
No way you can get any of the above combinations from doing this.

Maroun
  • 94,125
  • 30
  • 188
  • 241
2

Yes. To supplement the reasons described in the other answers, a few binary examples make it pretty clear that it will not be possible to make the result greater than either of the args:

         0
         1
    ------
         0

         1
         1
    ------
         1

    111011
     11111
    ------
     11011   

    111011
    111011
    ------
    111011

Given the two arguments, the highest that we can achieve is if both of the arguments are the same value, the result being equal to the value of the two arguments (last example above).

It is impossible to make the result larger no matter what we set the arguments to. If you are able to, then we are in serious trouble. ;)

acarlon
  • 16,764
  • 7
  • 75
  • 94
1

n & m has all the bits that are set in m and in n.

~n & m has all the bits that are set in m but not in n.

Adding both quantities will give all the bits that are set in m. That is, m:

m = (n & m) + (~n & m)

m ≥ (n & m)
sam hocevar
  • 11,853
  • 5
  • 49
  • 68