12

I ran into a strange problem. To demonstrate, let's take the largest unsigned number on my machine (printf "%X \n" -1 gives me FFFFFFFFFFFFFFFF), and try to shift some bits.  First, shift to the left:

printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF<<4 ))
FFFFFFFFFFFFFFF0
printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF<<8 ))
FFFFFFFFFFFFFF00
printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF<<16 ))
FFFFFFFFFFFF0000

So far so good. As expected. Now let's try the right shift:

printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF>>4 ))
FFFFFFFFFFFFFFFF
printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF>>8 ))
FFFFFFFFFFFFFFFF
printf "%X \n" $(( 0xFFFFFFFFFFFFFFFF>>16 ))
FFFFFFFFFFFFFFFF

Wait, what?? Why is this not working? Is that a bug?


Edit:

I am dreading that someone will suggest some connection with the sign bit being raised. But we are not talking about arithmetic, so the concept of sign has no place here. Other tools like * and / are for arithmetic. The whole point of having a tool that can manipulate bits is to be able to manipulate bits -- no matter how I'll chose to display those bits later, as signed or as unsigned. Right? Like:

printf "%u \n" -1
18446744073709551615

Any ideas anybody?

EDIT:

Since the answers here went straight to talking about multiplication or division, let me try to explain my concern more clearly. Multiplication/division and bit-shifting are two different things, although I can see the connection between them in the minds of long-time programmers. When doing arithmetic, you have to have the concept of sign; for bit-shifting you don't. Bash has given us two distinctly different sets of tools for these two different things. When I want to multiply a number by 2, I reach for the * tool. The fact that under the hood Bash can use bit-shifts for arithmetic is beyond the point.

To quote one of the answers...

If the sign bit wasn't copied, the result would turn into an unsigned number. E.g. shifting the 8-bit value 1111 0000 once to the right would give 0111 1000

But turning 1111 0000 into 0111 1000 is exactly what I want. If I wanted to do a division, then I would use arithmetic operstor instead.

Anyway, is there at least some way of explicitly specifying with what kind of bits it should fill when shifting?

6
  • what does this give you? ... printf "%X \n" $(( 0x7FFFFFFFFFFFFFFF>>16 ))
    – jsotola
    Apr 4 at 3:50
  • 1
    "When doing arithmetic, you have to have the concept of sign; for bit-shifting you don't." -- well, except that like at least two answers below say (and said before you added that statement), for "arithmetic" shifts, the sign (bit) does matter very much. Like it or not, that's the answer to what you asked, the reason you're not getting the result you wish. Now, if you want Bash to implement an unsigned shift, you might be better off asking the maintainer to implement it, instead of trying to argue here how the current situation should not be.
    – ilkkachu
    Apr 4 at 8:04
  • 1
    @ilkkachu No, it's not my intention to argue, I was just trully amazed by what I discovered, as I'm coming from a language (Forth) where bit-shifts are simply just that. The more I reread these answers here, the more I can't see for what possible sane reason would Bash force me to connect bitshifting to arithmetic. I mean, what is then even the point of giving me bitwise operators? I realize that there's probably nothing I can do though. Thank you.
    – Pourko
    Apr 4 at 8:24
  • @Pourko, it's not just Bash, you get the same with all the shells. And like I tried to say in my answer, it's tied to how it's done in C. (Probably because originally that was the straightforward implementation, and it stuck. Now of course POSIX describes it so). So the real question is, why does C do it like that, and I'm guessing that it makes sense, because there you can pick an unsigned type, which then wouldn't have issues with a sign bit. But for the shell, it's more useful in general to have signed values, and, bit fiddling probably isn't considered the main purpose of a shell.
    – ilkkachu
    Apr 4 at 8:34
  • @ilkkachu I understand that bit fiddling isn't considered the main purpose of a shell, but then why even give me bit fiddling operators, if they're going to cripple them? Anyway, as there's nothing I can fo about it, I am accepting your answer. Thank you.
    – Pourko
    Apr 4 at 8:40
13

There are two different ways to shift right in common use.

The "logical right shift" inserts zero bits on the left, so the result of shifting one bit to the right corresponds to dividing the unsigned binary number by two. echo $(( 16 >> 1 )) gives 8.

And, the "arithmetic right shift" inserts a copy of the sign bit on the left, so the result of shifting one bit to the right corresponds to dividing the signed binary number by two. echo $(( 16 >> 1 )) gives 8, and echo $(( -16 >> 1 )) gives -8. Except that on two's complement numbers, it doesn't match the rounding of an actual division: -15 >> 1 gives -8; while -15 / 2 gives -7.

If the sign bit wasn't copied, but zeroed, the result would be a positive number. E.g. shifting the 8-bit value 1111 0000 (0xf0, -16) once to the right would give 0111 1000 (0x78, +120).


Now, which one of these is used is a hairier matter.

In practice, many implementations would use the arithmetic shift for signed numbers, and shell arithmetic is mostly done on a signed long.

But that's not exactly guaranteed, at all. The POSIX definition for shell arithmetic refers to the C standard for most of the behaviour, and e.g. the operator table doesn't say anything about what sort of a shift >> is supposed to be. (see: Shell Command Language, 2.6.4 Arithmetic Expansion and Shell & Utilities, 1.1.2 Concepts Derived from the ISO C Standard: Arithmetic Precision and Operations)

Integer variables and constants, including the values of operands and option-arguments, [...] shall be implemented as equivalent to the ISO C standard signed long data type [...]

Arithmetic operators and control flow keywords shall be implemented as equivalent to those in the cited ISO C standard section, [...]
<<, >>: Section 6.5.7, Bitwise Shift Operators

cppreference.com says of the C operators that

For negative a, the value of a >> b is implementation-defined (in most implementations, this performs arithmetic right shift, so that the result remains negative).

(That may be a remnant of a world where not everything was two's complement. A shift to the right of a ones' complement or a sign-magnitude number would be different from the shift to the right of a two's complement number. But the result is the same: implementation-defined it is.)

Some other programming languages, like Javascript, have distinct operators for arithmetic right shift >>, and logical right shift >>>. But C doesn't, and neither do any of the shells I tried.

As an aside, if you were to do shifts with offsets greater than the word width, you'd also see strange things happen. On an x86, 1 << 64 is just 1, because the processor only looks at the lowest 6 bits of the shift value, so it's the same as 1 << 0. (1 << 32) << 32 is 0, though, and the result might be different on another processor.


You said,

But the concept of sign has no place here. I mean, a number is a number, regardless of whether later you'll chose to display it as signed or unsigned, right?

And that's true for addition, subtraction, and the low part of a multiplication (e.g. 32x32 -> 32) on a two's complement machine.

But it's not true for the high part of a multiplication or division in general. The 8-bit value 0xff can mean the unsigned number 255 or the signed number -1. An 8x8 -> 16 multiplication for e.g. 0xff * 0xff is either 0x0001 or 0xfe01, depending on if it's signed (-1 * -1) or unsigned (255 * 255). Also e.g. 0xff / 3 is either 0 or 0x55, depending on if it's signed (-1 / 3 == 0), or unsigned (255 / 3 == 85).

8
  • I understand what you are saying, but multiplication and bit-shifting are two different things. Multiplication has the concept of sign, bit-shifting doesn't. That you can short-cut one to the other under the hood in your assembler primitives, that doesn't make them the same thing.
    – Pourko
    Apr 3 at 12:31
  • 2
    @Pourko, yes, they are different things. But still the fact is that there are commonly three types of shifts: left shift, inserting zeroes on the right; "logical" right shift, inserting zeroes on the left; and "arithmetic" right shift, copying the sign bit on the left. You might want to use just the "logical" variant at all times, and I don't blame you. But since the "arithmetic" variant exists, I guess someone has found uses for it, and in any case, like it or not, that's what you're likely to get in the shell.
    – ilkkachu
    Apr 3 at 12:34
  • "Likely to get", since it's implementation defined in C. So on some other machine, you could get other results for the right shift. I would avoid shifting signed numbers, to be honest.
    – ilkkachu
    Apr 3 at 12:35
  • "avoid shifting signed numbers"... well, that's exactly what I needed to do actually.:-) Anyway, wasn't there an option to specify what kind of bits you want to fill with? I remember seeing something like printf %x $((0xffffff>>8|0xCC)) -- doesn't work -- gives me ffff.
    – Pourko
    Apr 3 at 12:58
  • @Pourko, well, as a 64-bit (or 32-bit) number, 0xffffff (16777215) is positive. So yeah, if you have a 64-bit system but you only deal with the lowest 63 bits (or less), then everything is positive and you can ignore the sign bit. Just and with 0x7fffffffffffffff or 0xffffffff or whatever in every turn. Or write the stuff you need in another language, probably C since I don't think too many of the "scripting" languages have unsigned integers.
    – ilkkachu
    Apr 3 at 13:02
10
  • Logical right shifts fills with zeroes,

    [01010110] >> 2 becomes [00010101]
    [11010110] >> 2 becomes [00110101]
    
  • Arithmetic right shifts fills with the most significant bit,

    [01010110] >> 2 becomes [00010101]
    [11010110] >> 2 becomes [11110101]
    

You expect logical shift, but Bash performs an arithmetic shift. This does have to do with signedness.

The manual says

Evaluation is done in fixed-width integers. The operators and their precedence, associativity, and values are the same as in the C language.

Integer constants follow the C language definition, without suffixes or character constants. Constants with a leading 0 are interpreted as octal numbers. A leading ‘0x’ or ‘0X’ denotes hexadecimal.

And quoting from Computer Systems, Randal Bryant & David O'Hallaron:

The C standards do not precisely define which type of right shift should be used. For unsigned data, right shifts must be logical. For signed data (the default), either arithmetic or logical shifts may be used. (...) In practice, however, almost all compiler/machine combinations use arithmetic right shifts for signed data, and many programmers assume this to be the case.

This has also been asked in Stack Overflow: Are the shift operators (<<, >>) arithmetic or logical in C?

3

Bash behaves like other shells. It's arguably a design bug that shells provide limited-size arithmetic rather than normal integer arithmetic despite being a fairly high-level language, but at this point in time, it isn't going to change.

a number is a number, regardless of whether later you'll chose to display it as signed or unsigned, right?

Yes, a number is a number. But shells don't have actual integers. They only have machine integers, which are more limited and behave in strange ways.

Multiplication/division and bit-shifting are two different things, although I can see the connection between them in the minds of long-time programmers. When doing arithmetic, you have to have the concept of sign; for bit-shifting you don't.

Indeed they are different, but related things, and that's precisely what you misunderstand. Bit shifting definitely has a concept of sign!

An machine integer can be interpreted in several different ways:

  • As an array of N value bits. This is the representation in memory.
  • As an array of bits, the first of which is the sign bit and the other N-1 are value bits. The sign bit is the most significant bit of the N-value-bits interpretation
  • As an integer between 0 and 2^N-1 (“unsigned integers”), whose value is expressed by the N value bits.
  • As an integer between -2^(N-1) and 2^(N-1)-1 (“signed integers”), whose value is expressed by the N-1 value bits and the sign bit. If the sign bit is 0, the value is given by the value bits. If the sign bit is 1, the value is negative, and in theory there are several ways this value can be calculated from the value bits, but in practice I don't know of any platform that runs a Unix shell and does something other than two's complement. With a two's complement representation, the value of an integer whose sign bit is 1 and whose value bits represent x is - (2^(N-1) - x).
  • As an integer modulo 2^N (“integers modulo”). The value is the unsigned value modulo 2^N. In two's complement representation, this is also the signed value modulo 2^N (this is a major advantage of two's complement).

As long as all numbers involved are between 0 and 2^N-1, you can pick any interpretation, and all the operations will give the intuitive result. However, if an operand or the result is outside this range (negative, or too large), it matters which interpretation you use.

I'll give examples with N=4 (2^N = 16) and two's complement to keep the examples readable. In practice, in modern versions of bash, N=64. In ancient versions of bash and in other shells, N may be 32 on 32-bit platforms.

  • Number parsing is performed modulo 2^N. For example, with N=4, 3 and 19 and -13 all represent the same number, with the bit representation 0011, while -3 and 13 all have the bit representation 1101.
  • Octal and hexadecimal printing treat the number as an unsigned integer. For example, the number with the bit representation 1101 is printed out as d in hexadecimal: its first bit is interpreted as a value bit, not as a sign bit.
  • Decimal printing treats the number as a signed integer. For example, the number with the bit representation 1101 is printed out as -3 in hexadecimal: its first bit is interpreted as a sign bit, not as a value bit.
  • Addition, subtraction and multiplication are performed modulo 2^N. This is equivalent to performing the operation on unsigned integers or signed integers without a range limit, then taking the remainder modulo 2^N inside the desired range.
  • Division is performed on signed integers. Unlike addition, subtraction and multiplication, this choice of representation matters: using unsigned integers or numbers modulo would give different results. (There is one twist: (-2^(N-1) / -1) is the only case where the result is out of range. As far as I know, all shells give it the value -2^(N-1).)
  • Bitwise operations operate on the bit representation. For most operations, it doesn't matter whether you pick the signed or unsigned representation: the same operations are performed on all bits. However, for shifts, it does matter, and:
    • A left shift treats the first bit as a value bit. For example, the number with the bit representation 0111 shifted left by 1 has the bit representation 1110. This makes a left shift by k equivalent to multiplying by 2^k.
    • In all shells I've ever seen, a right shift treats the first bit as a sign bit which is propagated onto the value bits. For example, the number with the bit representation 1101 shifted right by 1 has the bit representation 1110. This makes a right shift by k equivalent to dividing by 2^k. This is called an arithmetic shift, .
  • Comparisons work on signed integers. For example, the number with the bit representation 1111 is smaller than the number with the bit representation 0000, since 1111 is considered negative.

And so, getting back to 64-bit examples, 0xFFFFFFFFFFFFFFFF>>4 is 0xFFFFFFFFFFFFFFFF, because >> interprets its left operand as a signed bit array and propagates the sign bit, which is set, onto the 4 value bit positions that are opened at the top. The operation is exactly the same as -1 >> 4, because -1 and 0xFFFFFFFFFFFFFFFF are just different ways of representing the same machine integer.

1
  • "With a two's complement representation, the value of an integer whose sign bit is 1 and whose value bits represent x is 2^N - x" -- should that be -2^(N-1) + x ? The four-bit signed value 1111 would be -2^3 + 7 = -8 + 7 = -1. Or, -2^3 + 2^2 + 2^1 + 2^0; in effect the sign bit has the same positional value as usual, but negative sign.
    – ilkkachu
    Apr 4 at 8:13
-1

Have a look at .

As the first 1 (from left) represents the sign, it is simply reproduced on. If you try:

printf "%X \n" $(( 0x7FFFFFFFFFFFFFFF>>4 ))

you may get, what you expected.

4
  • 2
    Fot what possible sane reason would it be "simply reproduced on"? And no, I don't have the number 0x7FFFFFFFFFFFFFFF readily available, without some knowledge about the bitness of the machine I'm running on, and also about how Bash is compiled (32?64?)
    – Pourko
    Apr 3 at 10:01
  • Good question, but not for me, the bitwise operation manual has to be consulted. You have to take in account, you are using signed integer, and you have no carry bit.
    – schweik
    Apr 3 at 10:06
  • 1
    @schweik He can print that same number as either signerd ot unsigned. So what does sign have to do with it?
    – Ardwena
    Apr 3 at 10:09
  • 2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.