Bit length of int or long?

[Darrell Gallion]

"Carey Evans" 
> I found when rewriting crypt() in Python that nearly all the right
> shifts were by constants, so I could write something like
> 
>     ((t >> 18) & 0x3fff)
> 
> to trim off the sign bits.

Yeah, but...
>>> x=0xffffffff
>>> x
-1
>>> hex((x>>18)&0x3fffffff)
'0x3fffffff'
>>> hex((x>>2)&0x3fffffff)
'0x3fffffff'
>>> hex((x>>5)&0x3fffffff)
'0x3fffffff'
>>>

You inspired me to write :)

import sys, string, re

class BitMath:

    def __init__(self, negOne=-1):
        self._maskCache={}
        self._negOne=negOne # Just in case word sizes want to change.
        self._wordSize=self.bitLen(negOne)
        self._signBitMask= 1 << (self._wordSize-1)
        self._signBitMaskRightOne= 1 << (self._wordSize-2)

    def test(self):
        pat=re.compile("test.")
        dic=self.__class__.__dict__
        for n in dic.keys():
            if pat.match(n):
                dic[n](self)

    def getMask(self, sz):
        """
        Return a mask of binary ones of len sz
        """
        if self._maskCache.has_key(sz):
            return self._maskCache[sz]

        rm = sz%4
        dic={0:'', 1:'1', 2:'3', 3:'7'}
        res=['0x',dic[rm]]

        for x in range(sz/4):
            res.append('f')

        val=eval(string.join(res,''))
        self._maskCache[sz]=val
        return val

    def testGetMask(self):
        for c in range(33):
            val=self.getMask(c)
            assert(val==self.shift(-1,-(32-c)))

    def bitLen(self, x, wordLen=32):
        """
        From Guido's post.
        Fixed to handle unsigned numbers
        Doesn't work with negative longs
        >>> hex(0xfL ^ 0x80000000)
        '-0x7FFFFFF1L'
        >>> hex(0xf ^ 0x80000000)
        '0x8000000f'
        """
        global signBitMask
        n = 0
        if x > 0:
            while x:
                n = n+1
                x = x>>1
        elif x == -1:
            assert(type(x) != type(1L))
            n= wordLen
        else:
            assert(type(x) != type(1L))
            n= self.bitLen(x ^ self._signBitMask)+1
        return n

    def testBitLen(self):
        assert(self.bitLen(-1)==32)
        assert(self.bitLen(0xf)==4)
        assert(self.bitLen(999999999999999L)==50)

    def shift(self, x, cnt):
        """
        shift right if cnt > 0
        shift left  if cnt < 0
        Right shift fills with zeros
        """
        if cnt==0:
            return x

        y=x
        if x > 0 or cnt > 0:
            if cnt < 0:
                y = x >> -cnt
            elif cnt > 0:
                y = x << cnt
        else:
            x = x ^ self._signBitMask
            y = x >> 1
            y = y | self._signBitMaskRightOne
            y = y >> (-cnt-1)

        return y

    def testShift(self):
        assert(self.shift(-1, -2)  == 0x3fffffff)
        assert(self.shift(-1, -32) == 0)
        assert(self.shift(0xf, 4) == 0xf0)
        assert(self.shift(0xa5000000, -8) == 0xa50000)

    def showShift(self):
        """
        Demo shift
        """
        def show(start, func):
            for c in range(10):
                res=func(start, c)
                print "%-4d%08x%15d"%(c, res, res)
            print "*"*50

        show(-1, self.shift)
        show(sys.maxint, self.shift)

    def rotate(self, x, cnt):
        """
        rotate bits by cnt
        Bits are recirculated to the opposite end
        """
        if cnt==0:
            return x

        bitLx   = self.bitLen(x)
        cnt1= (cnt % self._wordSize)
        temp1= self.shift(x, -(self._wordSize - cnt1))
        temp2= self.shift(x, cnt1)
        return temp2 | temp1

    def testRotate(self):
        last=1
        for c in range(10):
            if 0:
                print "%08x"%self.rotate(0xa5000000,-c*4)
                print "%08x"%self.rotate(0xa5000000,c*4)
                print '-----------'

            temp=self.rotate(1,c*4)
            if temp > last:
                assert(temp == last * 16)
            else:
                assert(temp==1)
            last=temp


bitMath=BitMath()
bitMath.test()
bitMath.showShift()