Make negative numbers positive, shift them and make them negative again:

sub SRshift { 
    $_[0] < 0 
        ? -( -$_[0] >> $_[1] ) 
        :     $_[0] >> $_[1] 
}
[download]

Should work on any platform regardless of native integer size.

Thanks. This is the most elegant way I've seen so far, and I think I now understand the math of what exactly it is I'm trying to do. (I would vote this up but I'm now out of votes for the day; I only got 2.)

"(1 << $firstbit)" seems to be a constant. Extract it from the loop and it should be faster.

You could remove the loop completely by (in the case of 32 bit) checking the high-bit, then shifting for $y, then or-ing with $FFFFFFFF shifted left 32-$y

Slowly, please. :-) Bitwise anything is new to me, and I struggle with even understanding what it means.

Yes, I can see how (1 << $firstbit) is a constant. But its purpose is to get at that first bit, 0b10000000000000000000000000000000, i.e. 2**31. What is a better way to do that? I originally had "2**$firstbit" in place of "(1 << $firstbit)". Would that be better here? Is that what you mean by 'extracting' it?

As for your second paragraph, you'll have to slow down and explain how to do what you're saying, as you lost me completely with everything beginning with "checking the high-bit."

In any case, thanks!

He was suggesting that you do something like:

my $firstbit = ($longsize * 8) - 1;
my $firstbit_mask = 1 << $firstbit;
[download]

then use $firstbit_mask instead of 1 << $firstbit_mask. This cuts down on the number of shifts to do.

---

As for the second paragraph:

use constant NUM_BITS = $Config{ivsize} * 8;
use constant SIGN_BIT = 1 << ( NUM_BITS - 1 );
use constant ALL_BITS = -1;

sub sr_signed {
   my ($p, $q) = @_;
   if ($p & SIGN_BIT) {
      return ($p >> $q) | ($ALL_BITS << (NUM_BITS - $q));
   } else {
      return $p >> $q;
   }
}
[download]

Example:

Shift 10101111...10101100 by 3

     10101111...10101100 >> 3
     ||||||||   |||||
      \\\\\\\\   \\\\\
       \\\\\\\\   \\\\\
        ||||||||   |||||
     00010101111...10101

     11111111...11111111 << (NUM_BITS-3)
                     |||
       _____________///
      ///
     |||
     11100000...00000000

     00010101111...10101
   | 11100000...00000000
     -------------------
     11110101111...10101
[download]

(Note that ivsize should be used, not longsize.)

a) if you do something in a loop that is executed 32 times, that something is done 32 times. If you do it before the loop it is only done once. That should make anything faster. So you could do this:

my $highbitset= (1<< $firstbit);

foreach ...
   ... $x & $highbitset) != 0);
[download]

As you can see the bitshift is only done once and inside the loop the constant contents of the variable is used instead.

b) What you do is (for negative 32bit numbers): loop $y times: shift by one, set the high bit, shift by one, set the high bit ...

What you could do: No loop, just shift by $y. set all high bits at once (With high bits I mean all the bits shifted in as 0 instead of 1).

And the value you need to set all high-bits at once would be what? 0b10000... if $y==1, 0b11000.... if $y==2, and so on to 0b1111... if $y=32. This value is just 0b111111.... shifted left 32-$y times, i.e. 0b1111.... << 32-$y.

More generally I would specify that as -1 << ($longsize*8 - $y)

(What I'm trying to do with all this is implement Paj's JavaScript MD5 library in Perl, ...)

Your bit fiddling question is certainly an interesting one, and I don't want to spoil the fun... but in case you just want to get the job done, you could also use the existing Digest::MD5 core module:

$ perl -MDigest::MD5=md5_hex -E 'say md5_hex("message digest")'
f96b697d7cb7938d525a2f31aaf161d0
[download]

The signed shift can be implemented in terms of a division:

sub sr_i32 {
   my ($p, $q) = @_;
   return int( $p / (2<<$q) );
}
[download]

Note that divisions by power of two are lossless.

Update: Previous implementation only worked with q=1, so provided a different implementation.

You could eliminate the loop pretty easily.

#!/usr/bin/perl

use strict;
use warnings 'all';
use Config;

my $longsize = $Config{longsize};
my $bits = $longsize * 8;

sub rshift { # Should be signed/sign-propagating right shift
    my ($x, $y) = @_;
    my $mask = 0; 
    my $z = $x >> $y;
    $mask = (2 ** ($y + 1) -1) << ($bits - $y) if $x < 0;
    return $z | $mask;
}
[download]

It won't be very easy to turn it into an infix operator in Perl 5 without using a source filter... and you really don't want to go there if you don't have to.

UPDATE:Or if you want to calculate native size a different way:

#!/usr/bin/perl

use strict;
use warnings 'all';

my $bits;
{
    my $native = -1;
    $bits++ while $native >>= 1;
} 

sub rshift { # Should be signed/sign-propagating right shift
    my ($x, $y) = @_;
    my $mask = 0; 
    my $z = $x >> $y;
    $mask = ( -1 >> ($bits - $y) ) << ($bits - $y) if $x < 0;
    return $z | $mask;
}
[download]

Thanks for all the helpful replies. Another little question that's bugging me (I'm not sure if anybody will see this down here or not): does my function presume endian-ness of one form or another? Or does that even matter? Whether big-endian or little-endian, the leftmost bit of the leftmost byte will be the sign bit, correct? Will the endian-ness of the integer affect how it is shifted? It doesn't appear to so far, since even on my little-endian Win32 system, I get the correct end result. And it doesn't seem to matter if I remove the ">" from my pack and unpack there at the end -- I get the correct result. As I said, my understanding of the binary system is still pretty new.

endianness may become important if you store numbers as binary data in a string (with the pack function) or on disk. It is important in languages like C that allow you to use the memory cells your integers are stored in as any other data type.

Perl (and many other interpreted languages) don't allow this. You can't access the memory cells of your variables directly. If you use your integer variable as a string a conversion will be done by the interpreter. '>>' and other functions know the endianness of the system and use it. That is even true for C.

Note that you can specify endianness when you use the pack function.