7

From Hacker's Delight: 2nd Edition:

Formula to turn off the rightmost 1-bit of a word.

The formula here seems a little bit awkward here. How is some x vector is subtracted from 1 vector (presumbly 0x1111 1111) when x is smaller than 1? (Like: (as given in example) 0x0101 1000 - 0x0000 0000 doesn't make any sense to me) The former is a smaller number than the first one and the words aren't storing signed vectors either. Is that something related to RISC specific here or what?

As specified in the notation section of the book. A bold letter corresponds a vector for word like x = 00000000. And a bold one differs from a light face 1. As bold 1 = 11111111 which is an 8 bit word.

Edit2: Special Thanks to Paul Hankin to figure out the unconventional notations used here. A bold faced one refers to 32 bit size word which is [00000001] and a light faced 1 refers to a number one as in C.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
RewCie
  • 183
  • 1
  • 9
  • When you subtract 1 from a number, all the rightmost zeros carry until a 1 is found. Then, since you are subtracting 1, this is turned into a zero and the zeros of before are turned into 1s. Looking at this new number from the right you see that it has all ones where `x` has zeros and then it has a zero (while `x` has 1), after this the two numbers are equals. ANDing them will then only clear the rightmost 1 of `x`. Simply put, subtracting 1 will NOT the rightmost sequence made of a 1 followed by zero or more 0. Doing this on a paper will greatly help you visualize it. Try a few cases. – Margaret Bloom Oct 30 '20 at 08:44
  • You mention vectors in the question, but that's a mistake -- there's no vectors, only unsigned integers. The 0s and 1s are the binary representation of the number used for explanatory purposes only. – Paul Hankin Oct 30 '20 at 08:45
  • It's not clear what you mean by "0x1111 1111"r. "0x" usually represents a number in hexadecimal, and there's nothing like that in the text you quote. "x is smaller than 1" also doesn't make sense - the only unsigned integer smaller than 1 is 0. – Paul Hankin Oct 30 '20 at 08:50
  • 1
    `x` is a number. `1` is also a number. There are no vectors in sight. If `x` is `5`, then `x-1` is `4`. – n. m. could be an AI Oct 30 '20 at 09:13
  • @MargaretBloom I'm afraid. The 1 is written in bold letters here (which means it's a vector corresponding to 11111111). So how subtraction of some word say for x=00001111 (8 bit word will proceed?) How can you perform 00001111-11111111 here? – RewCie Oct 30 '20 at 09:16
  • "The 1 is written in bold letters here (which means it's a vector corresponding to 11111111)." No, it doesn't mean anything like that. 1 is the number 1. There is no convention that bold numbers mean vectors. – n. m. could be an AI Oct 30 '20 at 09:22
  • @PaulHankin well the author has explicitly mentioned light faced 1 when needed and in the notations part states that bold faced alphabets are vectors corresponding to 32 bit word size – RewCie Oct 30 '20 at 09:23
  • @n.'pronouns'm. well there are light faced 1 too written when needed along with bold faced 1. That's confusing... :( – RewCie Oct 30 '20 at 09:24
  • Yes, I'm looking at section 1-1 of the book and I see your confusion. It uses "vector" to mean a fixed-length sequence of bits with the usual (computer) arithmetic defined on them. **1** represents the "vector" 00000001. I'm not sure the book's defintion is helpful and it's certainly not standard. For example **00000000 - 00000001 = 11111111**. The more usual way to define this is modulo 256 arithemetic. – Paul Hankin Oct 30 '20 at 09:25
  • @PaulHankin oh, then what's the meaning of light faced 1? – RewCie Oct 30 '20 at 09:27
  • If the text makes sense when a bold 1 is interpreted as the number 1, and doesn't make sense when the same bold 1 is interpreted as a vector of 1 bits, then one plausible explanation of this phenomenon is that bold 1 should be interpreted as the number 1, rather than as a vector of 1 bits. You are welcome to look for other explanations but you probably won't find any, – n. m. could be an AI Oct 30 '20 at 09:29
  • 2
    light faced 1 is a number. bold 1 is a fixed-length vector of 0's and 1's that represents the binary form of 1 (eg: **00000001**). bold faced addition is "vector addition" as defined by the book, which corresponds to computer arithmetic, not what everyone else in the world means by vector addition. – Paul Hankin Oct 30 '20 at 09:30
  • @n.'pronouns'm. certainly the bold faced 1 is a fixed size binary word 00000001 and light faced 1 is a number. That makes sense. Thanks :) – RewCie Oct 30 '20 at 09:32
  • 1
    If you think about C, bold-faced numbers represent machine words and light-faced numbers represent regular numbers. That's the intention obscured by the book's definitions – Paul Hankin Oct 30 '20 at 09:32
  • @PaulHankin Ooooooooooo I now see!!! Thank you very much :) that was certainly helpful! This new subject with a mysterious notations was haunting me since! I'm glad to decode them with your help :-) thank you very much! – RewCie Oct 30 '20 at 09:34

2 Answers2

8

Subtracting 1

Since we're more familiar with decimal than with binary, it sometimes helps to look at what happens in decimal.

What happens when subtracting 1 in decimal? Take for example 1786000 - 1 = 1785999.

If you subtract 1 from a positive number x in decimal:

  • all the zeroes at the right of x become 9;
  • the rightmost nonzero digit of x becomes 1 less;
  • other digits are unaffected.

Now, in binary, it works exactly the same, except we only have 0 1 instead of 0 123456789.

If you subtract 1 from a number x in binary:

  • all the zeroes at the right of x become 1;
  • the rightmost nonzero bit of x becomes 0;
  • other bits are unaffected.

What about negative numbers? Happily, representation using 2's complement is such that negative numbers behave exactly like positive numbers. In fact, when looking at the bits of x, you can subtract 1 from x without needing to know whether x is a signed int or an unsigned int.

x & (x-1)

Let's start with an example: x = 01011000. We can subtract 1 the way I just explained:

x   = 01011000
x-1 = 01010111

Now what's the result of the bitwise-and operation x & (x-1)? We take the two bits in each column; if they are both 1, we write 1; if at least one of them is 0, we write 0.

x       = 01011000
x-1     = 01010111
x&(x-1) = 01010000

What happened?

  • all the zeroes at the right of x remain zero;
  • the rightmost 1 of x becomes a 0 because of x-1;
  • all other bits are unaffected, because they are the same in x and x-1.

Conclusion: we have zeroed the rightmost 1 of x, and left all other bits unaffected.

Stef
  • 13,242
  • 2
  • 17
  • 28
4

Let's take a look at an what x-1 does. Assume x is a value '???? 1000 (? are 0 or 1)
=> x-1 = ???? 0111
=> x & (x-1) = ???? 0000

It's very similar no matter where the right most 1 is placed within x.

Requested example:
x=00001111
=> x-1=00001110
=> x & (x-1) = 00001110

P.s. x-1 = 00001110 - 00000001 (<=> 00001110 + 11111111)

MrSmith42
  • 9,961
  • 6
  • 38
  • 49
  • Can you show doing the same thing for x as something like x=00001111? (x-1) here is equivalent to (00001111-11111111). How will you proceed here? – RewCie Oct 30 '20 at 09:13
  • Actually it's opposite! @Paul Hankin decoded it. Vector 1 refers to [00000001] and light faced 1 as [11111111] thanks for the demonstration of required example :) – RewCie Oct 30 '20 at 09:36
  • 1
    See also https://catonmat.net/low-level-bit-hacks for more worked examples of this clear-lowest-set, and other bithacks. – Peter Cordes Nov 03 '20 at 08:42