Re: bitshift of int8, int16, etc?

[David Bateman]

Daniel J Sebald wrote:
> David Bateman wrote:
>> I believe the attached patch is what is needed to make the bitshift of
>> signed integer types the same as bitshifts of floating point numbers
>>
>> D.
> 
> The patch to the header file seems to sweep the whole code tree, so
> recompiling takes a while.  Anyway, the following commands should
> display the whole spectrum of results, which is easier to consider than
> having to follow complementation given there is the type of variable to
> consider, and I have no experience with the inttypes.h behavior:
> 
> range = int8(reshape([-128:127],16,16))
> bitshift(range,1)
> 
> octave:4> range = int8(reshape([-128:127],16,16))
> range =
> 
> -128 -112  -96  -80  -64  -48  -32  -16    0   16   32   48   64   80  
> 96  112
> -127 -111  -95  -79  -63  -47  -31  -15    1   17   33   49   65   81  
> 97  113
> -126 -110  -94  -78  -62  -46  -30  -14    2   18   34   50   66   82  
> 98  114
> -125 -109  -93  -77  -61  -45  -29  -13    3   19   35   51   67   83  
> 99  115
> -124 -108  -92  -76  -60  -44  -28  -12    4   20   36   52   68   84 
> 100  116
> -123 -107  -91  -75  -59  -43  -27  -11    5   21   37   53   69   85 
> 101  117
> -122 -106  -90  -74  -58  -42  -26  -10    6   22   38   54   70   86 
> 102  118
> -121 -105  -89  -73  -57  -41  -25   -9    7   23   39   55   71   87 
> 103  119
> -120 -104  -88  -72  -56  -40  -24   -8    8   24   40   56   72   88 
> 104  120
> -119 -103  -87  -71  -55  -39  -23   -7    9   25   41   57   73   89 
> 105  121
> -118 -102  -86  -70  -54  -38  -22   -6   10   26   42   58   74   90 
> 106  122
> -117 -101  -85  -69  -53  -37  -21   -5   11   27   43   59   75   91 
> 107  123
> -116 -100  -84  -68  -52  -36  -20   -4   12   28   44   60   76   92 
> 108  124
> -115  -99  -83  -67  -51  -35  -19   -3   13   29   45   61   77   93 
> 109  125
> -114  -98  -82  -66  -50  -34  -18   -2   14   30   46   62   78   94 
> 110  126
> -113  -97  -81  -65  -49  -33  -17   -1   15   31   47   63   79   95 
> 111  127
> 
> octave:5> bitshift(range,1)
> ans =
> 
>    0   32   64   96 -128  -96  -64  -32    0   32   64   96 -128  -96 
> -64  -32
>    2   34   66   98 -126  -94  -62  -30    2   34   66   98 -126  -94 
> -62  -30
>    4   36   68  100 -124  -92  -60  -28    4   36   68  100 -124  -92 
> -60  -28
>    6   38   70  102 -122  -90  -58  -26    6   38   70  102 -122  -90 
> -58  -26
>    8   40   72  104 -120  -88  -56  -24    8   40   72  104 -120  -88 
> -56  -24
>   10   42   74  106 -118  -86  -54  -22   10   42   74  106 -118  -86 
> -54  -22
>   12   44   76  108 -116  -84  -52  -20   12   44   76  108 -116  -84 
> -52  -20
>   14   46   78  110 -114  -82  -50  -18   14   46   78  110 -114  -82 
> -50  -18
>   16   48   80  112 -112  -80  -48  -16   16   48   80  112 -112  -80 
> -48  -16
>   18   50   82  114 -110  -78  -46  -14   18   50   82  114 -110  -78 
> -46  -14
>   20   52   84  116 -108  -76  -44  -12   20   52   84  116 -108  -76 
> -44  -12
>   22   54   86  118 -106  -74  -42  -10   22   54   86  118 -106  -74 
> -42  -10
>   24   56   88  120 -104  -72  -40   -8   24   56   88  120 -104  -72 
> -40   -8
>   26   58   90  122 -102  -70  -38   -6   26   58   90  122 -102  -70 
> -38   -6
>   28   60   92  124 -100  -68  -36   -4   28   60   92  124 -100  -68 
> -36   -4
>   30   62   94  126  -98  -66  -34   -2   30   62   94  126  -98  -66 
> -34   -2
> 
> This is much preferred to the existing CVS behavior.  That behavior has
> columns of zeros along the right end.  Mapping so many values to zero in
> a somewhat meaningless way is bad because it loses information that
> shouldn't be lost.
> 
> Now as to including the sign bit in the shift, how about looking at it
> the following way?  Shifting left 1 bit is analogous to multiplying by
> two, i.e., adding the value to itself.
> 
> -127 + (-127)
> 
>  10000001
>  10000001
>  --------
> 100000010
> 
> truncated to 00000010 becomes 2.  OK, I'm good with the patch.
> 

This is the standard behavior of an arithmetic shift.. See

http://en.wikipedia.org/wiki/Arithmetic_shift


> There are other prefered behaviors for shift.  Say for example the user
> wants saturation (-127 << 1 => -128 and 126 << 1 => 127) rather than
> wrap around, which one could use in signal processing.  But that might
> be a type other than int8.

Ok, saturation might make sense. My preference was or an arithmetic
shift as a shift operator that had a clear and documented functionality.
If we got with a saturation we are defining our own operator (which is
fine of course). Ok, I'd be happy with saturation, but I don't see an
efficient implmentation.

> 
> The lack of overflow information concerns me a bit.  Should or shouldn't
> that be worked into the code?

As with << and >> in C, its up to the user. I suppose we could set a
warning that is normally off, that would flag an overflow.

In any case, what would you propose as a patch

D.