FST  openfst-1.7.1
OpenFst Library
nthbit.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 
4 #ifndef FST_EXTENSIONS_NGRAM_NTHBIT_H_
5 #define FST_EXTENSIONS_NGRAM_NTHBIT_H_
6 
7 #include <fst/types.h>
8 
10 
11 inline uint32 nth_bit(uint64 v, uint32 r) {
12  uint32 shift = 0;
13  uint32 c = __builtin_popcount(v & 0xffffffff);
14  uint32 mask = -(r > c);
15  r -= c & mask;
16  shift += (32 & mask);
17 
18  c = __builtin_popcount((v >> shift) & 0xffff);
19  mask = -(r > c);
20  r -= c & mask;
21  shift += (16 & mask);
22 
23  c = __builtin_popcount((v >> shift) & 0xff);
24  mask = -(r > c);
25  r -= c & mask;
26  shift += (8 & mask);
27 
28  return shift +
29  ((nth_bit_bit_offset[(v >> shift) & 0xff] >> ((r - 1) << 2)) & 0xf);
30 }
31 
32 #endif // FST_EXTENSIONS_NGRAM_NTHBIT_H_
uint32 nth_bit(uint64 v, uint32 r)
Definition: nthbit.h:11
uint64_t uint64
Definition: types.h:32
uint32_t uint32
Definition: types.h:31
uint32 nth_bit_bit_offset[]
Definition: nthbit.cc:28