chiark / gitweb /
Eliminate string_login().
[disorder] / lib / bits.c
1 /*
2  * This file is part of DisOrder
3  * Copyright (C) 2008 Richard Kettlewell
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  * 
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  * 
15  * You should have received a copy of the GNU General Public License
16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  */
18
19 /** @file lib/bits.c
20  * @brief Bit operations
21  */
22
23 #include "common.h"
24
25 #include <math.h>
26
27 #include "bits.h"
28
29 #if !HAVE_FLS
30 /** @brief Compute index of leftmost 1 bit
31  * @param n Integer
32  * @return Index of leftmost 1 bit or -1
33  *
34  * For positive @p n we return the index of the leftmost bit of @p n.  For
35  * instance @c leftmost_bit(1) returns 0, @c leftmost_bit(15) returns 3, etc.
36  *
37  * If @p n is zero then -1 is returned.
38  */
39 int leftmost_bit(uint32_t n) {
40   /* See e.g. Hacker's Delight s5-3 (p81) for where the idea comes from.
41    * Warren is computing the number of leading zeroes, but that's not quite
42    * what I wanted.  Also this version should be more portable than his, which
43    * inspects the bytes of the floating point number directly.
44    */
45   int x;
46   frexp((double)n, &x);
47   /* This gives: n = m * 2^x, where 0.5 <= m < 1 and x is an integer.
48    *
49    * If we take log2 of either side then we have:
50    *    log2(n) = x + log2 m
51    *
52    * We know that 0.5 <= m < 1 => -1 <= log2 m < 0.  So we floor either side:
53    *
54    *    floor(log2(n)) = x - 1
55    *
56    * What is floor(log2(n))?  Well, consider that:
57    *
58    *    2^k <= z < 2^(k+1)  =>  floor(log2(z)) = k.
59    *
60    * But 2^k <= z < 2^(k+1) is the same as saying that the leftmost bit of z is
61    * bit k.
62    *
63    *
64    * Warren adds 0.5 first, to deal with the case when n=0.  However frexp()
65    * guarantees to return x=0 when n=0, so we get the right answer without that
66    * step.
67    */
68   return x - 1;
69 }
70 #endif
71
72 /*
73 Local Variables:
74 c-basic-offset:2
75 comment-column:40
76 fill-column:79
77 indent-tabs-mode:nil
78 End:
79 */