15

2¹⁶-1 & 2⁵ = 2⁵ (or? obviously ?)

A developer asked me today what is bitwise 65535 & 32 i.e. 2¹⁶-1 & 2⁵ = ? I thought at first spontaneously 32 but it seemed to easy whereupon I thought for several minutes and then answered 32. 32 seems to have been the correct answer but how? 65535=2¹⁶-1=1111111111111111 (but it doesn't seem right since this binary number all ones should be -1(?)), 32 = 100000 but I could not convert that in my head whereupon I anyway answered 32 since I had to answer something. Is the answer 32 in fact trivial? Is in the same way 2¹⁶-1 & 2⁵-1 =31? Why did the developer ask me about exactly 65535?

Binary what I was asked to evaluate was 1111111111111111 & 100000 but I don't understand why 1111111111111111 is not -1. Shouldn't it be -1? Is 65535 a number that gives overflow and how do I know that?

Niklas Rosencrantz
  • 8,008
  • 17
  • 56
  • 95
  • 4
    There must be something special. It reminds me of 56 6635, the Czech national standard for beer. Hmmmm...time for a beer. – joshp Nov 22 '12 at 22:35
  • 5
    You make too many assuptions: 65535 gives -1 only in 16-bit two's complement arithmetic. It gives -0 in 16-bit one's complement arithmetic and 65535 in 32-bit two's complement and one's complement arithmetics. – mouviciel Nov 25 '13 at 08:25
  • 4
    It is the upper limit of TCP ports. – Renae Lider Oct 05 '14 at 09:48

3 Answers3

27

The number is treated as an unsigned integer in this case which means all bits set will not produce -1 (if it were signed then yes, you would be correct). So all 16 bits set will give you 65535.

Interestingly enough though, signed state isn't a factor when doing logic bit-operations. Bits are themselves not signed as they are the lowest component in a computer. It's specified by the cpu operation if the bits in ex. a register will be treated signed or unsigned.

Negative numbers are produced by setting the most significant bit (MSB) to true IF the number is treated as signed (which "side", or which outer bit will be set varies depending on cpu architecture, ie. big-endian / little-endian) .

Community
  • 1
epistemex
  • 543
  • 3
  • 6
  • 9
    Most modern machines convert to negative by flipping the bits and adding one: 2's complement. Just setting one bit gives you the problem of having +0 and -0. – James Nov 22 '12 at 21:14
  • 1
    That isn't necessarily a problem. 1's complement truncates toward zero, regardless of result sign. 2's complement truncates toward -infinity. In certain applications, this can get you into trouble. – John R. Strohm Jan 10 '13 at 18:04
19

It is trivial. 65535 in binary is all ones, so ANDing it with any X less than 65535 will give you X.

ggambetta
  • 1,204
  • 9
  • 8
10

Answering the second part of your question. You've tagged it as so, 65535 in 32 bits is 00000000000000001111111111111111, signed or unsigned it is not -1.

Martijn Pieters
  • 14,499
  • 10
  • 57
  • 58
Chris Kent
  • 219
  • 2
  • 6