1/* mpz_tstbit -- test a specified bit. 2 3Copyright 2000, 2002 Free Software Foundation, Inc. 4 5This file is part of the GNU MP Library. 6 7The GNU MP Library is free software; you can redistribute it and/or modify 8it under the terms of the GNU Lesser General Public License as published by 9the Free Software Foundation; either version 3 of the License, or (at your 10option) any later version. 11 12The GNU MP Library is distributed in the hope that it will be useful, but 13WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 14or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15License for more details. 16 17You should have received a copy of the GNU Lesser General Public License 18along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 19 20#include "gmp.h" 21#include "gmp-impl.h" 22 23 24/* For negatives the effective twos complement is achieved by negating the 25 limb tested, either with a ones or twos complement. Twos complement 26 ("-") is used if there's only zero limbs below the one being tested. 27 Ones complement ("~") is used if there's a non-zero below. Note that "-" 28 is correct even if the limb examined is 0 (and the true beginning of twos 29 complement is further up). 30 31 Testing the limbs below p is unavoidable on negatives, but will usually 32 need to examine only *(p-1). The search is done from *(p-1) down to 33 *u_ptr, since that might give better cache locality, and because a 34 non-zero limb is perhaps a touch more likely in the middle of a number 35 than at the low end. 36 37 Bits past the end of available data simply follow sign of u. Notice that 38 the limb_index >= abs_size test covers u=0 too. */ 39 40int 41mpz_tstbit (mpz_srcptr u, mp_bitcnt_t bit_index) 42{ 43 mp_srcptr u_ptr = PTR(u); 44 mp_size_t size = SIZ(u); 45 unsigned abs_size = ABS(size); 46 mp_size_t limb_index = bit_index / GMP_NUMB_BITS; 47 mp_srcptr p = u_ptr + limb_index; 48 mp_limb_t limb; 49 50 if (limb_index >= abs_size) 51 return (size < 0); 52 53 limb = *p; 54 if (size < 0) 55 { 56 limb = -limb; /* twos complement */ 57 58 while (p != u_ptr) 59 { 60 p--; 61 if (*p != 0) 62 { 63 limb--; /* make it a ones complement instead */ 64 break; 65 } 66 } 67 } 68 69 return (limb >> (bit_index % GMP_NUMB_BITS)) & 1; 70} 71