intmath.hh revision 2
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_H__ 30#define __INTMATH_H__ 31 32// Returns the prime number one less than n. 33int PrevPrime(int n); 34 35// Determine if a number is prime 36inline bool 37IsPrime(int n) 38{ 39 int i; 40 41 if (n == 2 || n == 3) 42 return true; 43 44 // Don't try every odd number to prove if it is a prime. 45 // Toggle between every 2nd and 4th number. 46 // (This is because every 6th odd number is divisible by 3.) 47 for (i = 5; i*i <= n; i += 6) { 48 if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 49 return false; 50 } 51 } 52 53 return true; 54} 55 56inline unsigned 57LeastSigBit(unsigned n) 58{ return n & ~(n - 1); } 59 60inline bool 61IsPowerOf2(unsigned n) 62{ return n != 0 && LeastSigBit(n) == n; } 63 64inline int 65FloorLog2(unsigned x) 66{ 67 if (x == 0) 68 return -1; 69 70 int y = 0; 71 72 if (x & 0xffff0000) { y += 16; x >>= 16; } 73 if (x & 0x0000ff00) { y += 8; x >>= 8; } 74 if (x & 0x000000f0) { y += 4; x >>= 4; } 75 if (x & 0x0000000c) { y += 2; x >>= 2; } 76 if (x & 0x00000002) { y += 1; } 77 78 return y; 79} 80 81inline int 82CeilLog2(unsigned n) 83{ return FloorLog2(n-1)+1; } 84 85inline unsigned 86FloorPow2(unsigned n) 87{ return 1 << FloorLog2(n); } 88 89inline unsigned 90CeilPow2(unsigned n) 91{ return 1 << CeilLog2(n); } 92 93inline bool 94IsHex(char c) 95{ return (c >= '0' && c <= '9' || 96 c >= 'A' && c <= 'F' || 97 c >= 'a' && c <= 'f'); 98} 99 100inline bool 101IsOct(char c) 102{ return (c >= '0' && c <= '7'); } 103 104inline bool 105IsDec(char c) 106{ return (c >= '0' && c <= '9'); } 107 108inline int 109Hex2Int(char c) 110{ 111 if (c >= '0' && c <= '9') 112 return (c - '0'); 113 114 if(c >= 'A' && c <= 'F') 115 return (c - 'A') + 10; 116 117 if (c >= 'a' && c <= 'f') 118 return (c - 'a') + 10; 119 120 return 0; 121} 122 123#endif // __INTMATH_H__ 124