1 /* ffs.c -- find the first set bit in a word. 2 Copyright (C) 2011-2021 Free Software Foundation, Inc. 3 4 This file is free software: you can redistribute it and/or modify 5 it under the terms of the GNU Lesser General Public License as 6 published by the Free Software Foundation; either version 2.1 of the 7 License, or (at your option) any later version. 8 9 This file is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU Lesser General Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public License 15 along with this program. If not, see <https://www.gnu.org/licenses/>. */ 16 17 /* Written by Eric Blake. */ 18 19 #include <config.h> 20 21 /* Specification. */ 22 #include <strings.h> 23 24 #include <limits.h> 25 26 #if defined _MSC_VER && !(__clang_major__ >= 4) 27 # include <intrin.h> 28 #endif 29 30 int 31 ffs (int i) /* */ 32 { 33 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__clang_major__ >= 4) 34 return __builtin_ffs (i); 35 #elif defined _MSC_VER 36 /* _BitScanForward 37 <https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64> */ 38 unsigned long bit; 39 if (_BitScanForward (&bit, i)) 40 return bit + 1; 41 else 42 return 0; 43 #else 44 /* <https://github.com/gibsjose/BitHacks> 45 gives this deBruijn constant for a branch-less computation, although 46 that table counted trailing zeros rather than bit position. This 47 requires 32-bit int, we fall back to a naive algorithm on the rare 48 platforms where that assumption is not true. */ 49 if (CHAR_BIT * sizeof i == 32) 50 { 51 static unsigned int table[] = { 52 1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9, 53 32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10 54 }; 55 unsigned int u = i; 56 unsigned int bit = u & -u; 57 return table[(bit * 0x077cb531U) >> 27] - !i; 58 } 59 else 60 { 61 unsigned int j; 62 for (j = 0; j < CHAR_BIT * sizeof i; j++) 63 if (i & (1U << j)) 64 return j + 1; 65 return 0; 66 } 67 #endif 68 }