Functions for fiddling with bits. More...

#include "binary.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

Functions
static int	nlz32 (uint32_t x)
	Number of leading zeroes in 32-bit unsigned integer. More...

uint32_t	rev32 (uint32_t x)
	Reverse bits in a 32-bit integer. More...

uint64_t	rev64 (uint64_t x)
	Reverse bits in a 64-bit integer. More...

int	nlz64 (uint64_t x)
	Number of leading zeroes in 64-bit unsigned integer. More...

tipId_t	low_bits_on (unsigned n)

int	nlz (tipId_t x)
	Number of leading zeroes in tipId_t variable.

void	printBits (size_t size, void const const ptr, FILE fp)
	Print the bits in an object of size "size", pointed to by "ptr". More...

int	getBits (tipId_t x, int maxbits, int bit[maxbits])
	Examine the bits in x. More...

void	printWhichBits (size_t const size, void const *const ptr)
	Print the (0-based) indices of the bits that are "on". More...

int	num1bits (tipId_t x)
	Count the number of 1 bits in x. More...

tipId_t	next_power_of_2 (tipId_t x)
	Round up to the next largest power of 2.

uint32_t	uint32Hash (uint32_t key)
	Hash function for a 32-bit integer. More...

uint32_t	uint64Hash (uint64_t key)
	Hash function for a 64-bit integer.

int	no_shared_bits (int n, tipId_t *tid)
	Return 1 if the values in array share no bits; 0 otherwise. More...

Detailed Description

Functions for fiddling with bits.

Copyright: Copyright (c) 2016, Alan R. Rogers roger.nosp@m.s@an.nosp@m.thro..nosp@m.utah.nosp@m..edu. This file is released under the Internet Systems Consortium License, which can be found in file "LICENSE".

Function Documentation

◆ getBits()

int getBits	(	tipId_t	x,
		int	maxbits,
		int	bit[maxbits]
	)

Examine the bits in x.

If bit i equals 1, then add i to array bit. Return the number of nonzero bits. maxbits is the allocated length of array bit. It is an error if the number of nonzero bits exceeds maxbits.

◆ nlz32()

static int nlz32 ( uint32_t x )

static

Number of leading zeroes in 32-bit unsigned integer.

From p 99 of Hacker's Delight, 2nd edition.

Referenced by nlz().

◆ nlz64()

int nlz64 ( uint64_t x )

Number of leading zeroes in 64-bit unsigned integer.

64-bit version of algorithm on p 99 of Hacker's Delight, 2nd edition.

Referenced by nlz().

◆ no_shared_bits()

int no_shared_bits	(	int	n,
		tipId_t *	tid
	)

Return 1 if the values in array share no bits; 0 otherwise.

Returns 1 if n==0.

◆ num1bits()

int num1bits ( tipId_t x )

Count the number of 1 bits in x.

From p 85 of Hacker's Delight, 2nd Edn, by Henry S. Warren, Jr. This algorithm is fast when the number of 1 bits is small, and it makes no assumption about the number of bits in x.

Returns: the number of bits.

Referenced by BranchTab_collapse(), BranchTab_rmPops(), compare_tipId(), and comparePtrs().

◆ printBits()

void printBits	(	size_t	size,
		void const *const	ptr,
		FILE *	fp
	)

Print the bits in an object of size "size", pointed to by "ptr".

Assumes little endian

◆ printWhichBits()

void printWhichBits	(	size_t const	size,
		void const *const	ptr
	)

Print the (0-based) indices of the bits that are "on".

Parameters

[in]	ptr	points to the object whose bits will be examined
[in]	size	the size of the object in bytes

◆ rev32()

uint32_t rev32 ( uint32_t x )

Reverse bits in a 32-bit integer.

p 129 of Hacker's Delight, 2nd edn.

◆ rev64()

uint64_t rev64 ( uint64_t x )

Reverse bits in a 64-bit integer.

This just extends the pattern in rev32.

◆ uint32Hash()

uint32_t uint32Hash ( uint32_t key )

Hash function for a 32-bit integer.

From Thomas Wang's 1997 article: https://gist.github.com/badboy/6267743 This generates integer overflows, presumably by design.