bit_scan.c File Reference

SIP-router core ::Module: SIP-router core. More...

#include "bit_scan.h"

Include dependency graph for bit_scan.c:

Go to the source code of this file.

Variables

• unsigned char _debruijn_hash32 [32]

  use a de Bruijn sequence to get the index of the set bit for a number of the form 2^k (DEBRUIJN_HASH32() and DEBRUIJN_HASH64()).
  

---

Detailed Description

Definition in file bit_scan.c.

---

Variable Documentation

unsigned char _debruijn_hash32[32]

Initial value:

{0, 1, 2, 6, 3, 11, 7, 16, 4, 14, 12, 21, 8,
        23, 17, 26, 31, 5, 10, 15, 13, 20, 22, 25, 30, 9, 19, 24, 29, 18, 28, 27 }

bit_scan_forward & bit_scan_reverse would need first to convert the argument to 2^k (where k is the first set bit or last set bit index)- For bit_scan_forward this can be done very fast using x & (-x). For more info about this method see: http://citeseer.ist.psu.edu/leiserson98using.html ("Using de Bruijn Sequences to Index a 1 in a Computer Word")

Definition at line 36 of file bit_scan.c.