Copyright	(c) Edward Kmett 2013-2014
License	BSD3
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	experimental
Portability	non-portable
Safe Haskell	Trustworthy
Language	Haskell2010

Data.Bits.Extras

Description

Calculate a number of fiddly bit operations using fast de Bruijn multiplication tables.

Synopsis

class (Num t, FiniteBits t) => Ranked t where
- lsb :: t -> Int
- rank :: t -> Int
- nlz :: t -> Int
log2 :: Word32 -> Int
word32Log2 :: Word32 -> Int
msb :: Ranked t => t -> Int
w8 :: Integral a => a -> Word8
w16 :: Integral a => a -> Word16
w32 :: Integral a => a -> Word32
w64 :: Integral a => a -> Word64
assignBit :: Bits b => b -> Int -> Bool -> b
zeroBits :: Bits a => a
oneBits :: FiniteBits b => b
unsafeOneBits :: Bits b => b
srl :: Bits b => b -> Int -> b

Documentation

class (Num t, FiniteBits t) => Ranked t where Source #

Minimal complete definition

nlz

Methods

lsb :: t -> Int Source #

Calculate the least significant set bit using a debruijn multiplication table. NB: The result of this function is undefined when given 0.

rank :: t -> Int Source #

Calculate the number of trailing 0 bits.

nlz :: t -> Int Source #

Calculate the number of leading zeros.

Instances

Instances details

Ranked Int8 Source #
Instance details Defined in Data.Bits.Extras Methods lsb :: Int8 -> Int Source # rank :: Int8 -> Int Source # nlz :: Int8 -> Int Source #
Ranked Int16 Source #
Instance details Defined in Data.Bits.Extras Methods lsb :: Int16 -> Int Source # rank :: Int16 -> Int Source # nlz :: Int16 -> Int Source #
Ranked Int32 Source #
Instance details Defined in Data.Bits.Extras Methods lsb :: Int32 -> Int Source # rank :: Int32 -> Int Source # nlz :: Int32 -> Int Source #
Ranked Int64 Source #
Instance details Defined in Data.Bits.Extras Methods lsb :: Int64 -> Int Source # rank :: Int64 -> Int Source # nlz :: Int64 -> Int Source #
Ranked Word8 Source #
Instance details Defined in Data.Bits.Extras Methods lsb :: Word8 -> Int Source # rank :: Word8 -> Int Source # nlz :: Word8 -> Int Source #
Ranked Word16 Source #
Instance details Defined in Data.Bits.Extras Methods lsb :: Word16 -> Int Source # rank :: Word16 -> Int Source # nlz :: Word16 -> Int Source #
Ranked Word32 Source #
Instance details Defined in Data.Bits.Extras Methods lsb :: Word32 -> Int Source # rank :: Word32 -> Int Source # nlz :: Word32 -> Int Source #
Ranked Word64 Source #
Instance details Defined in Data.Bits.Extras Methods lsb :: Word64 -> Int Source # rank :: Word64 -> Int Source # nlz :: Word64 -> Int Source #

log2 :: Word32 -> Int Source #

word32Log2 :: Word32 -> Int Source #

msb :: Ranked t => t -> Int Source #

Calculate the most significant set bit.

w8 :: Integral a => a -> Word8 Source #

w16 :: Integral a => a -> Word16 Source #

w32 :: Integral a => a -> Word32 Source #

w64 :: Integral a => a -> Word64 Source #

assignBit :: Bits b => b -> Int -> Bool -> b Source #

zeroBits :: Bits a => a #

zeroBits is the value with all bits unset.

The following laws ought to hold (for all valid bit indices n):

```
clearBit zeroBits n == zeroBits
```
```
setBit   zeroBits n == bit n
```
```
testBit  zeroBits n == False
```
```
popCount zeroBits   == 0
```

This method uses clearBit (bit 0) 0 as its default implementation (which ought to be equivalent to zeroBits for types which possess a 0th bit).

Since: base-4.7.0.0

oneBits :: FiniteBits b => b Source #

A more concise version of complement zeroBits.

>>> complement (zeroBits :: Word) == (oneBits :: Word)
True

>>> complement (oneBits :: Word) == (zeroBits :: Word)
True

Note

The constraint on oneBits is arguably too strong. However, as some types (such as Natural) have undefined complement, this is the only safe choice.

unsafeOneBits :: Bits b => b Source #

A version of oneBits that weakens the context from FiniteBits to Bits. This is unsafe because there are some data types with Bits instances that have undefined complement, such as Natural. Nevertheless, it is sometimes useful to call this function on data types without FiniteBits instances (e.g., Integer), so this function is provided as a convenience.

srl :: Bits b => b -> Int -> b Source #

Shift Right Logical (i.e., without sign extension)

NB: When used on negative Integers, hilarity may ensue.