Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Two's complement – You beauty

everyogi.in

Post reply on HN
Print view View original

31–40 of 92 posts

Re: Two's complement – You beauty

#32

Post by alipang »

gizmo686 wrote: post #22
vog wrote: post #6

This all is suddenly less surprising for people who learned some modulo arithmetics in school (or university). That is, calculating with the remainders of division. For example: - Calculating "modulo 60" means calculating time with a round clock in mind, considering only minutes and ignoring hours (and seconds). - Calculating with angles (in degrees) means just calculating "modulo 360". - "modulo 1000" means calculat…

I didn't downvote you. However, I am a math person and your post feels wrong for some reason. It isn't wrong, but it feels like it should be; and I am not entirely sure why. CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement. The insight with two's complement is that we can interperet the "upper" half of numbers as negative. As…

https://en.wikipedia.org/wiki/Method_of_complements

Re: Two's complement – You beauty

#34

Post by colejohnson66 »

laszlokorte wrote: post #33

A widget I built last year for interactively visualizing a number circle with various binary interpretations: https://thesis.laszlokorte.de/demo/number-circle.html

That's really cool! However, I can drag the SVG's viewbox around; something I wouldn't expect to be able to do.

EDIT: It makes sense when you zoom in (like you would with 7 bits), but if I'm zoomed out all the way, I wouldn't' expect to be able to pan around. I'd expect it to prevent panning past the edge.

Re: Two's complement – You beauty

#35

Post by todd8 »

yellowapple wrote: post #28
1010111 wrote: post #17

Shitty C code: the binary printing function is needlessly complicated. void print_bin(int x){ for(unsigned m=~(~0u>>1); m ; m>>=1) putchar(x&m?'1':'0'); putchar('\n'); }

Shitty C code: I've seen Perl golfs more readable than this. The article's code is more explicit and verbose, which makes it easier for non-C-programmers (like myself) to actually understand what's going on.

Understandably confusing for a non-C-programmer, but it is idiomatic C. It's not code golf; it's just the way one does machine independent bit twiddling.

A mask is used to test each bit position in turn. The tests look like this if written using binary literals:

    0b1000 & x
    0b0100 & x
    0b0010 & x
    0b0001 & x
The '&' is the bitwise AND opperator in C. Of course, we'd have to do as many of these as the word size so 1010111 uses a for loop that starts with the first mask, a 1 in the leftmost position, and shifts it right one position every time through the loop (using the C right shift operator >> on an unsigned mask value). When the one bit is eventually shifted out the right side of the mask, the mask is all zeros so the loop terminates because zero acts like false in the for loop test.

The only other tricky thing is initializing the mask. To set only the leftmost bit in a word the code uses the bit complement operator ~ of C. Breaking it down for a four bit example looks like:

    0u          == 0b0000
    ~0u         == 0b1111
    ~0u >> 1    == 0b0111
    ~(~0u >> 1) == 0b1000
This is the expression that appears in the for loop initializing the mask value, and it works for any word size.

The original article's code was definitely not idiomatic, efficient, or safe (the memory allocation for an array of characters could fail and segfault). The book Hacker's Delight is a great reference for those wanting to understand how to do low level coding, a requirement for close to the hardware work like writing device drivers.

Re: Two's complement – You beauty

#36

Post by morecoffee »

Probably the most interesting part of 2's complement is how to negate numbers. Flip all the bits and add 1. Which is strange, because to negate the number again, flip all the bits and add 1. It feels like accidentally adding 2 doesn't it?

Re: Two's complement – You beauty

#37

Post by brandonbloom »

zardeh wrote: post #2

The python result should be expected. Python's integer type isn't sized, that is python will happily give you factorial(100), despite it being much larger than 64 bits. It can't then give you twos complement, because it can't know the size with which to complement the two.

That's a reasonable tradeoff for Python, but it's worth noting that there is a way to deal with this.

Quoting from http://reference.wolfram.com/language/tutorial/IntegerAndNum...

    Bitwise operations are used in various combinatorial
    algorithms. They are also commonly used in manipulating
    bitfields in low‐level computer languages. In such
    languages, however, integers normally have a limited
    number of digits, typically a multiple of 8. Bitwise
    operations in the Wolfram Language in effect allow
    integers to have an unlimited number of digits. When an
    integer is negative, it is taken to be represented in
    two's complement form, with an infinite sequence of ones
    on the left. This allows BitNot[n] to be equivalent
    simply to (-1 - n).

Re: Two's complement – You beauty

#38

Post by gpvos »

brandonbloom wrote: post #37
zardeh wrote: post #2

The python result should be expected. Python's integer type isn't sized, that is python will happily give you factorial(100), despite it being much larger than 64 bits. It can't then give you twos complement, because it can't know the size with which to complement the two.

That's a reasonable tradeoff for Python, but it's worth noting that there is a way to deal with this. Quoting from http://reference.wolfram.com/language/tutorial/IntegerAndNum... Bitwise operations are used in various combinatorial algorithms. They are also commonly used in manipulating bitfields in low‐level computer languages. In such languages, however, integers normally have a limited number of digits, typically…

Yes, but how would you print that infinite sequence of 1s?

Re: Two's complement – You beauty

#39

Post by d0mine »

yogeswarant wrote: post #3
zardeh wrote: post #2

The python result should be expected. Python's integer type isn't sized, that is python will happily give you factorial(100), despite it being much larger than 64 bits. It can't then give you twos complement, because it can't know the size with which to complement the two.

Thanks. Good to know this.

Bitwise opetations assume an infinite number of 1s on the left for negative numbers (2s compliment) e.g., ~-1 == 0 (-1 is an infinite number of 1s that are converted to 0 by ~ (invert) operator ).

  3 == 011
  2 == 010
  1 == 001
  0 == 000
  -1 == ..111
  -2 == ..110
  -3 == ..101

Re: Two's complement – You beauty

#40

Post by xxs »

yellowapple wrote: post #28
1010111 wrote: post #17

Shitty C code: the binary printing function is needlessly complicated. void print_bin(int x){ for(unsigned m=~(~0u>>1); m ; m>>=1) putchar(x&m?'1':'0'); putchar('\n'); }

Shitty C code: I've seen Perl golfs more readable than this. The article's code is more explicit and verbose, which makes it easier for non-C-programmers (like myself) to actually understand what's going on.

I think it's =much= easier to read compared to the one in the article. Although the usual approach is bit shifting the input and checking only the lowest/highest bit. Here is an example in Java:

  static void bin(int n) {		
    for (int i=0; i
Post reply on HN