intmath.hh revision 50
11039SN/A/* 21762SN/A * Copyright (c) 2003 The Regents of The University of Michigan 31039SN/A * All rights reserved. 41039SN/A * 51039SN/A * Redistribution and use in source and binary forms, with or without 61039SN/A * modification, are permitted provided that the following conditions are 71039SN/A * met: redistributions of source code must retain the above copyright 81039SN/A * notice, this list of conditions and the following disclaimer; 91039SN/A * redistributions in binary form must reproduce the above copyright 101039SN/A * notice, this list of conditions and the following disclaimer in the 111039SN/A * documentation and/or other materials provided with the distribution; 121039SN/A * neither the name of the copyright holders nor the names of its 131039SN/A * contributors may be used to endorse or promote products derived from 141039SN/A * this software without specific prior written permission. 151039SN/A * 161039SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 171039SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 181039SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 191039SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 201039SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 211039SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 221039SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 231039SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 241039SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 251039SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 261039SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu */ 282760Sbinkertn@umich.edu 292760Sbinkertn@umich.edu#ifndef __INTMATH_HH__ 301039SN/A#define __INTMATH_HH__ 311039SN/A 321039SN/A// Returns the prime number one less than n. 331039SN/Aint PrevPrime(int n); 341039SN/A 352521SN/A// Determine if a number is prime 361039SN/Atemplate <class T> 372521SN/Ainline bool 381039SN/AIsPrime(T n) 391039SN/A{ 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