1 /* 2 * Copyright 2013 Haiku, Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Paweł Dziepak, pdziepak@quarnos.org 7 */ 8 #ifndef KERNEL_UTIL_BITUTIL_H 9 #define KERNEL_UTIL_BITUTIL_H 10 11 12 #include <SupportDefs.h> 13 14 15 // http://graphics.stanford.edu/~seander/bithacks.html 16 static inline uint32 17 next_power_of_2(uint32 v) 18 { 19 v--; 20 v |= v >> 1; 21 v |= v >> 2; 22 v |= v >> 4; 23 v |= v >> 8; 24 v |= v >> 16; 25 v++; 26 27 return v; 28 } 29 30 31 // http://graphics.stanford.edu/~seander/bithacks.html 32 static inline uint32 33 count_set_bits(uint32 v) 34 { 35 v = v - ((v >> 1) & 0x55555555); 36 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 37 return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; 38 } 39 40 41 static inline uint32 42 log2(uint32 v) 43 { 44 static const int MultiplyDeBruijnBitPosition[32] = { 45 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 46 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 47 }; 48 49 v |= v >> 1; 50 v |= v >> 2; 51 v |= v >> 4; 52 v |= v >> 8; 53 v |= v >> 16; 54 55 return MultiplyDeBruijnBitPosition[(uint32)(v * 0x07C4ACDDU) >> 27]; 56 } 57 58 59 #endif // KERNEL_UTIL_BITUTIL_H 60 61