Understanding least significant byte operation

[Pablo Rozas Larraondo]

I have seen Go code using this function to find out the least significant byte of unsigned integers:

func LSB(ci uint64) uint64 { return uint64(ci) & -uint64(ci) }

This function works fine but I wonder why, if call the same AND operation, it results in an error: "constant -X overflows uint64"

Here is a playground example to illustrate this:

https://play.golang.org/p/_0EYtlLnmG

Does anyone know what changes when -uint64() is called in a return statement? How a negative uint should be interpreted?

Thank you,

Pablo

[Ayan George]

(-uint64(24)) is a constant that can't be represented by a uint64.

I think the relevant bit from the spec is:

"The values of typed constants must always be accurately representable
as values of the constant type. The following constant expressions are
illegal..."

BUT, the rules for expressions that cause overflow are well defined and
operations on the variable 'ci' abide by them.

So I think it is a matter of compile-time correctness vs runtime behavior.

The following also works:

https://play.golang.org/p/GYREFdz8-M

That is AFAIK. Someone please correct me if I'm wrong.

-ayan

[John Souvestre]

I believe that the result is the least significant bit, not byte.

 

John

    John Souvestre - New Orleans LA

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jan Mercl]

On Sun, Jul 23, 2017 at 7:26 PM John Souvestre <jo...@souvestre.com> wrote:

> I believe that the result is the least significant bit, not byte.

Does not look like that: https://play.golang.org/p/thzUaazLSp

--

-j

[Bakul Shah]

This is a standard trick to find the least significant set bit in a word. Only works for 2's complement numbers!

    -x == ~x+1

For example: x = 00110000b (24), ~x+1 = 11001111+1 = 11010000. Adding them yields 00010000; thus only the least significant set bit remains set.

Note that func LSB(x uint64) uint64 { return x&-x } works too. In your example you get an error because in Go literal constants are untyped. It is a pragmatic decision -- see https://blog.golang.org/constants

--

[John Souvestre]

Hi Jan.

 

Hmmm…  Here’s what I see.

 

00000000 00000000

00000001 00000001

00000010 00000010

00000011 00000001

00000100 00000100

00000101 00000001

…

11111100 00000100

11111101 00000001

11111110 00000010

11111111 00000001

 

That looks like the least significant set bit to me.

 

John

    John Souvestre - New Orleans LA

 

[Jan Mercl]

On Mon, Jul 24, 2017 at 12:25 AM John Souvestre <jo...@souvestre.com> wrote:

> That looks like the least significant set bit to me.

To me too ;-)

But I was responding to your

> On Sun, Jul 23, 2017 at 7:26 PM John Souvestre <jo...@souvestre.com> wrote:
>
>> I believe that the result is the least significant bit, not byte.

Where the word 'set' is not present.

--

-j

[Pablo Rozas Larraondo]

Thanks Bakul, I think I have a better understanding of what's going on after reading your response.

Is it correct to say that the Go compiler treats the prepended minus sign differently depending on the variable being a signed or an unsigned integer? 

By looking at this example: https://play.golang.org/p/feqQsuPkqk

It seems to me that in the case of an unsigned integer it's treated as a bitwise operation : -x == ^x + 1

But for signed integers -x == -1 * x

Cheers,

Pablo

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Matt Harden]

Both statements are true for both signed and unsigned integers.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[Pablo Rozas Larraondo]

Ok, I might be understanding this differently then:

The -1 * x operation cannot be defined for unsigned integers as -1 overflows. Therefore, -x in the case of unsigned types is interpreted differently by the compiler, resulting in a ^x + 1 operation. Is that a correct assumption?

By the way, yes, the title should say Bit instead of Byte, sorry about the confusion.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Bakul Shah]

[Sorry, didn't see your original response]

In the Go *language* (not just the compiler), when x is an unsigned int, -x is treated as a "shorthand" for ^x+1. Another interpretation is that for finite ints all arithmetic operations are modulo the word size. Thus -1 modulo 2^64 is 0xffffffff. You might even say that a 2's complement machine's native int type is an unsigned int! It is just that most arithmetic operations set relevant condition codes (or equivalent) that allows you (and the compiler) to interpret an int as a signed int or an unsigned one.

I would suggest reading up on how computers do arithmetic. Programming languages are merely syntactic sugar on top of processor instruction sets :-)

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[Matt Harden]

No, it's not interpreted differently. In 2's complement arithmetic, addition is the same operation on the underlying bits, whether the number is signed or unsigned. The same goes for negation and subtraction. There is a difference if you consider overflow, but Go doesn't have overflow of the integer types; they "wrap around" instead.

It so happens that if you look at the underlying bits, -x performs the exact same transformation on the bits as (~x+1). So they really end up being the same operation for signed and unsigned numbers. The "overflow" you're seeing is just a result of the way constants are handled in Go. The compiler detects overflow when you try to store a constant that's out of range into a variable, but overflow doesn't occur at runtime, only wraparound (all integer math is modulo 2^n for some n=8, 16, 32, or 64). Dividing (or modulo) by 0 is the only integer math that can fail at runtime, causing a panic.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[Pablo Rozas Larraondo]

Thanks Bakul, I also understand now what Matt Harden was referring to with his comment. At a bit level both operations cause the same effect on the underlying bits of the variable but it's meaning changes depending on the type. All clear!

Cheers,

Pablo

[Pablo Rozas Larraondo]

Thanks Matt. That's a very good explanation about the internal bit representation of integers and answers perfectly my question. I really appreciate your help in understanding these operations.

Cheers,

Pablo