0

I am confused by this, I thought that for signed integers the only difference is the first sign bit, but if that was thet was the case wouldn't e.g. 12 & -12 equal 12 (all bits are the same except for the first sign bit)?

Filip Kowalski
  • 178
  • 1
  • 11
  • 1
    Your confusion stems from an incorrect assumption that `12` and `-12` have the same bits except for the sign bit -- read about 2's complement – k_ssb May 17 '18 at 22:09
  • You may have read about floating point types without realising it: for those, it's far more common that `12.0` and `-12.0` only differ by a single bit. –  May 17 '18 at 22:12
  • this is not entirely duplicate. there is a second part, which is why is x&(-x) equal largest 2^k divisor. – thang May 17 '18 at 22:17
  • @thang Indeed. It may already be clear to the OP after reading the answers to that other question, but if not, if the OP edits the question to explain what part is still causing confusion, then that's a fair edit IMO and in that case the question should be re-opened. –  May 17 '18 at 22:33
  • Especially since he is somehow getting `x & (-x)` to equal something other than `1`. (always possible that the hardware does not use twos-compliment....) – David C. Rankin May 17 '18 at 22:38
  • @David C. Rankin `x & (-x)` only equals `1` if `x` is odd. – Mike Borkland May 17 '18 at 23:16
  • Quite right you are. Good catch. – David C. Rankin May 17 '18 at 23:19
  • op's statement actually is right. x&(-x) is the largest 2^k divisor of x. for odd x, k=0, obviously. the proof is pretty interesting, and, in fact, that statement is useful for optimizing a number of different bit banging algorithms. someone should reopen this question. – thang May 17 '18 at 23:20
  • @thang Yeah, I just thought of a skeleton for the proof in my head. Not too difficult if one understands the process of transforming `x` to `-x` (flip the bits and then add one). The proof would make a nice answer, although it would probably be more appropriate for Mathematics Stack Exchange. – Mike Borkland May 17 '18 at 23:41
  • naw, it's cool because it is applicable to code! the math stuff is just all talky talky :) basically -x = 2^n - x. let 2^n = sum(2^j,j=0,n-1)+1; represent x as a sum of powers of 2, and the answer falls out. it's pretty elegant. – thang May 18 '18 at 03:02

0 Answers0