classification
Title: Let shift operators take any integer value
Type: enhancement Stage:
Components: Interpreter Core Versions:
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: cmcqueen1975, dtorp, josiahcarlson, mark.dickinson, tim.peters
Priority: normal Keywords:

Created on 2005-05-19 19:54 by dtorp, last changed 2011-08-08 01:09 by cmcqueen1975. This issue is now closed.

Messages (15)
msg61195 - (view) Author: David Albert Torpey (dtorp) Date: 2005-05-19 19:54
Let:  
    1 >> -4 
be interpreted as:
    1 << 4

This should be easy to do.  It would be somewhat helpful for 
bit manipulations and multiplying by powers of two.  Without 
the change, my code is laced with sections like:

if y > 0:
    z = x << y
else:
    z = x >> -y

This is ugly and slow compared to a straight:
   z = x << y

There is a precedent.  See what is done with negative list 
indices for comparison.  It saves even less code with  x[len
(x)-i] becoming x[i].  The reason for doing it is code 
simplication and clarity.
msg61196 - (view) Author: Josiah Carlson (josiahcarlson) * (Python triager) Date: 2005-05-26 08:01
Logged In: YES 
user_id=341410

Is your code time critical?  Do your numbers have more than
53 bits of precision?  Do your numbers vary beyond 2**1024
or 1/2**1024?

If not, then the following should be sufficient for your
uses: int(x * 2**y)
msg61197 - (view) Author: David Albert Torpey (dtorp) Date: 2005-05-27 17:05
Logged In: YES 
user_id=681258

Yes, I use this on long integers.  And, the whole point of doing 
shifts is to avoid the costs of computing and multiplying by 
powers of two.  Besides the math equivalents do not express the 
algorithms as well or as directly as shifts.

Other than coming up with cumbersome workarounds (which I 
already had), do you have an objection to letting the shift 
operators use negative indices (in much the same way as with 
array indices)?
msg61198 - (view) Author: Josiah Carlson (josiahcarlson) * (Python triager) Date: 2005-05-27 18:06
Logged In: YES 
user_id=341410

Yes, I do have an objection.

On execution, either:
1. The interpreter would necessarily have to ask the
question "is this shift value positive or negative" in order
to possibly change which operation is to be executed.
2. Every shift operator would need to be rewritten to
support negative shift values.

Both of these solutions add compexity to what has been
historically (in all languages) a very simple operation, and
as the zen says "Simple is better than complex."

-1
msg61199 - (view) Author: David Albert Torpey (dtorp) Date: 2005-05-27 18:49
Logged In: YES 
user_id=681258

Forgive my directness, but the last post doesn't show the slightest 
clue about how Python works.  The existing test for a negative 
shift count takes place downstream from the interpreter in the 
int_lshift function in intobject.c (and the same for longobject.c).  
The RFE is to replace the line that raises a Value Error exception 
with a line that does something useful like flipping the sign of the 
argument and delegating to int_rshift.  That is a zero net change 
in code complexity.  The runtime of non-negative cases is 
likewise unchanged.  Is there someone else reading this who has 
an informed opinion?
msg61200 - (view) Author: Josiah Carlson (josiahcarlson) * (Python triager) Date: 2005-05-27 19:22
Logged In: YES 
user_id=341410

Pardon me for believing that your RFE was applicable to any
object with an __lshift__ method.  Being that you did not
explicitly state that it was for integers only, merely that
you did use it with integers.

Regardless, changing integers to support negative shifts
would imply that floats should also support negative shifts,
and that all objects supporting __(l|r)shift__ methods also
support negative shifts.  One of Python's strengths is about
consistancy, my rude friend, not merely about your
particular use case for negative shifts.

You should also realize that because this would be a new
feature, it would have to wait until Python 2.5, which has
at least a year before it is to be released.  Are you
willing to wait a year to use this?  If not, you should get
the source for 2.4, modify it as you see fit, and run your
own version.

If waiting a year for 2.5 and for your change to maybe be
included or running your own version of 2.4 is not
sufficient, then you have a serious problem on your hands,
and no one here can help you.
msg61201 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2005-05-27 19:50
Logged In: YES 
user_id=31435

-0.  I could live with this change, but would rather not.  In my 
experience complaints about using a negative shift count has 
correctly pointed out logic errors in my code, and I wouldn't 
want to lose that.

Note that floats don't support __[lr]shift__ regardless; neither 
do complex numbers nor Decimals; the benefit/damage 
among the builtin types would be confined to int & long.
msg61202 - (view) Author: David Albert Torpey (dtorp) Date: 2005-05-27 20:08
Logged In: YES 
user_id=681258

When balancing expressiveness against error checking, do you 
know what tipped the scales in favor of negative list indices?  I 
imagine the issues were similar (although shifting isn't nearly as 
common as shifting).
msg86412 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-04-24 14:37
Rejecting this due to:

 - no activity for almost 4 years
 - lack of positive responses

Also, I'm -1 on this change:  for me, a "x << n" that silently becomes 
"x >> -n" when n is negative would cause more harm than good.  In most 
of my uses, left and right shift for integers are quite different 
beasts:  a left shift represents an exact multiplication by a power of 
2, while a right shift loses information.
msg98308 - (view) Author: Craig McQueen (cmcqueen1975) Date: 2010-01-26 01:06
Just for the record... here is a relevant use case...

I'm working on some code for calculating CRCs, and hope to support any CRC width, including CRC-5. This involves, among the calculations:

    crc >> (crc_width - 8)

The complete expression is:

    crc = table[((crc >> (crc_width - 8)) ^ data_byte) & 0xFF] ^ (crc << 8)

where crc_width is typically 32 or 16, but in the case of CRC-5 would be 5.

I think the calculation would work fine for all cases, if only Python allowed me to right-shift with a negative number. But now I'll have to handle the two cases separately.
msg98325 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-01-26 10:56
Interesting.  I agree that that looks like a case where it would be desirable for a >> -n to do a << n.

By the way, I don't think your formula is quite correct:  your crc is going to grow unboundedly as extra data bytes come in.  I suspect that you want to mask the result with (1 << crc_width) - 1 after each update.
(And what's the '& 0xFF' for?  Isn't it redundant?)
msg98326 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-01-26 11:05
One other thought: you could always compute the expression

  crc >> (crc_width - 8)

as

  crc << 8 >> crc_width

Since you're computing crc << 8 anyway, this doesn't increase the operations count, so probably wouldn't significant impact performance.
msg98394 - (view) Author: Craig McQueen (cmcqueen1975) Date: 2010-01-27 00:38
Thanks, good points. I'm thinking with a C background and the fixed-width data types. The 0xFF could be needed if the data_byte is actually a larger number and you need to ensure only the lowest 8 bits are set. Or, if there is some sign-extending going on with the right-shift. That could happen in Python if the user passed a negative 'crc' in to the function (for whatever reason).

Yes, I'm missing a final mask. Thanks for pointing that out. I was thinking like a C programmer!

As for crc << 8 >> crc_width... the 'crc << 8' could bump an integer into long territory, making calculations slower. E.g.:

    >>> 2**23 << 8 >> 16
    32768L

    >>> 2**23 >> (16 - 8)
    32768
msg98396 - (view) Author: Craig McQueen (cmcqueen1975) Date: 2010-01-27 00:50
To complete that thought...

Since crc << 8 could bump the calculation into long territory, for that final mask I guess I'd want to mask and then shift. I.e. rather than

    crc_mask = ((1 << crc_width) - 1)
    crc = (...) ^ ((crc << 8) & crc_mask)

do:

    crc_lower_mask = ((1 << (crc_width - 8)) - 1)
    crc = (...) ^ ((crc & crc_lower_mask) << 8)

But that expression should evaluate to 0 if crc_width <= 8, so I guess I'll need to special-case it. And if I special-case it, I don't need to shift by a negative value after all!
msg141758 - (view) Author: Craig McQueen (cmcqueen1975) Date: 2011-08-08 01:09
So this has been rejected I see. Too bad, since I stub my metaphorical toe on this issue from time to time. Just for the record, here is an example:

http://stackoverflow.com/questions/4130936/perfect-hash-function/6976723#6976723
History
Date User Action Args
2011-08-08 01:09:15cmcqueen1975setmessages: + msg141758
2010-01-27 00:50:08cmcqueen1975setmessages: + msg98396
2010-01-27 00:38:46cmcqueen1975setmessages: + msg98394
2010-01-26 11:05:16mark.dickinsonsetmessages: + msg98326
2010-01-26 10:56:59mark.dickinsonsetmessages: + msg98325
2010-01-26 01:06:40cmcqueen1975setnosy: + cmcqueen1975
messages: + msg98308
2009-04-24 14:37:28mark.dickinsonsetstatus: open -> closed
resolution: rejected
messages: + msg86412
2009-01-30 20:40:27mark.dickinsonsetnosy: + mark.dickinson
2005-05-19 19:54:34dtorpcreate