intmath.hh revision 50
1/* 2 * Copyright (c) 2003 The Regents of The University of Michigan 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29#ifndef __INTMATH_HH__ 30#define __INTMATH_HH__ 31 32// Returns the prime number one less than n. 33int PrevPrime(int n); 34 35// Determine if a number is prime 36template <class T> 37inline bool 38IsPrime(T n) 39{ 40 T i; 41 42 if (n == 2 || n == 3) 43 return true; 44 45 // Don't try every odd number to prove if it is a prime. 46 // Toggle between every 2nd and 4th number. 47 // (This is because every 6th odd number is divisible by 3.) 48 for (i = 5; i*i <= n; i += 6) { 49 if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 50 return false; 51 } 52 } 53 54 return true; 55} 56 57template <class T> 58inline T 59LeastSigBit(T n) 60{ 61 return n & ~(n - 1); 62} 63 64template <class T> 65inline bool 66IsPowerOf2(T n) 67{ 68 return n != 0 && LeastSigBit(n) == n; 69} 70 71template <class T> 72inline int 73FloorLog2(T x) 74{ 75 if (x == 0) 76 return -1; 77 78 int y = 0; 79 80 if (x & 0xffff0000) { y += 16; x >>= 16; } 81 if (x & 0x0000ff00) { y += 8; x >>= 8; } 82 if (x & 0x000000f0) { y += 4; x >>= 4; } 83 if (x & 0x0000000c) { y += 2; x >>= 2; } 84 if (x & 0x00000002) { y += 1; } 85 86 return y; 87} 88 89template <class T> 90inline int 91CeilLog2(T n) 92{ 93 return FloorLog2(n - 1) + 1; 94} 95 96template <class T> 97inline T 98FloorPow2(T n) 99{ 100 return (T)1 << FloorLog2(n); 101} 102 103template <class T> 104inline T 105CeilPow2(T n) 106{ 107 return (T)1 << CeilLog2(n); 108} 109 110inline bool 111IsHex(char c) 112{ 113 return c >= '0' && c <= '9' || 114 c >= 'A' && c <= 'F' || 115 c >= 'a' && c <= 'f'; 116} 117 118inline bool 119IsOct(char c) 120{ 121 return c >= '0' && c <= '7'; 122} 123 124inline bool 125IsDec(char c) 126{ 127 return c >= '0' && c <= '9'; 128} 129 130inline int 131Hex2Int(char c) 132{ 133 if (c >= '0' && c <= '9') 134 return (c - '0'); 135 136 if(c >= 'A' && c <= 'F') 137 return (c - 'A') + 10; 138 139 if (c >= 'a' && c <= 'f') 140 return (c - 'a') + 10; 141 142 return 0; 143} 144 145#endif // __INTMATH_HH__ 146