OpenTTD
Functions | Variables
bitmath_func.cpp File Reference

Functions related to bit mathematics. More...

#include "../stdafx.h"
#include "bitmath_func.hpp"
#include "../safeguards.h"

Go to the source code of this file.

Functions

uint8 FindFirstBit (uint32 x)
 Search the first set bit in a 32 bit variable. More...
 
uint8 FindLastBit (uint64 x)
 Search the last set bit in a 64 bit variable. More...
 

Variables

const uint8 _ffb_64 [64]
 Lookup table to check which bit is set in a 6 bit variable. More...
 

Detailed Description

Functions related to bit mathematics.

Definition in file bitmath_func.cpp.

Function Documentation

◆ FindFirstBit()

uint8 FindFirstBit ( uint32  x)

Search the first set bit in a 32 bit variable.

This algorithm is a static implementation of a log congruence search algorithm. It checks the first half if there is a bit set search there further. And this way further. If no bit is set return 0.

Parameters
xThe value to search
Returns
The position of the first bit set

Definition at line 39 of file bitmath_func.cpp.

Referenced by AllocateMap(), and FindFirstBit2x64().

◆ FindLastBit()

uint8 FindLastBit ( uint64  x)

Search the last set bit in a 64 bit variable.

This algorithm is a static implementation of a log congruence search algorithm. It checks the second half if there is a bit set search there further. And this way further. If no bit is set return 0.

Parameters
xThe value to search
Returns
The position of the last bit set

Definition at line 67 of file bitmath_func.cpp.

Variable Documentation

◆ _ffb_64

const uint8 _ffb_64[64]
Initial value:
= {
0, 0, 1, 0, 2, 0, 1, 0,
3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0,
3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0,
3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0,
3, 0, 1, 0, 2, 0, 1, 0,
}

Lookup table to check which bit is set in a 6 bit variable.

Definition at line 17 of file bitmath_func.cpp.