1/* mpz_clrbit -- clear a specified bit. 2 3Copyright 1991, 1993, 1994, 1995, 2001, 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 23void 24mpz_clrbit (mpz_ptr d, mp_bitcnt_t bit_index) 25{ 26 mp_size_t dsize = d->_mp_size; 27 mp_ptr dp = d->_mp_d; 28 mp_size_t limb_index; 29 30 limb_index = bit_index / GMP_NUMB_BITS; 31 if (dsize >= 0) 32 { 33 if (limb_index < dsize) 34 { 35 mp_limb_t dlimb; 36 dlimb = dp[limb_index]; 37 dlimb &= ~((mp_limb_t) 1 << (bit_index % GMP_NUMB_BITS)); 38 dp[limb_index] = dlimb; 39 40 if (UNLIKELY (dlimb == 0 && limb_index == dsize-1)) 41 { 42 /* high limb became zero, must normalize */ 43 do { 44 dsize--; 45 } while (dsize > 0 && dp[dsize-1] == 0); 46 d->_mp_size = dsize; 47 } 48 } 49 else 50 ; 51 } 52 else 53 { 54 mp_size_t zero_bound; 55 56 /* Simulate two's complement arithmetic, i.e. simulate 57 1. Set OP = ~(OP - 1) [with infinitely many leading ones]. 58 2. clear the bit. 59 3. Set OP = ~OP + 1. */ 60 61 dsize = -dsize; 62 63 /* No upper bound on this loop, we're sure there's a non-zero limb 64 sooner ot later. */ 65 for (zero_bound = 0; ; zero_bound++) 66 if (dp[zero_bound] != 0) 67 break; 68 69 if (limb_index > zero_bound) 70 { 71 if (limb_index < dsize) 72 dp[limb_index] |= (mp_limb_t) 1 << (bit_index % GMP_NUMB_BITS); 73 else 74 { 75 /* Ugh. The bit should be cleared outside of the end of the 76 number. We have to increase the size of the number. */ 77 if (UNLIKELY (d->_mp_alloc < limb_index + 1)) 78 dp = _mpz_realloc (d, limb_index + 1); 79 80 MPN_ZERO (dp + dsize, limb_index - dsize); 81 dp[limb_index] = (mp_limb_t) 1 << (bit_index % GMP_NUMB_BITS); 82 d->_mp_size = -(limb_index + 1); 83 } 84 } 85 else if (limb_index == zero_bound) 86 { 87 dp[limb_index] = ((((dp[limb_index] - 1) 88 | ((mp_limb_t) 1 << (bit_index % GMP_NUMB_BITS))) + 1) 89 & GMP_NUMB_MASK); 90 if (dp[limb_index] == 0) 91 { 92 mp_size_t i; 93 for (i = limb_index + 1; i < dsize; i++) 94 { 95 dp[i] = (dp[i] + 1) & GMP_NUMB_MASK; 96 if (dp[i] != 0) 97 goto fin; 98 } 99 /* We got carry all way out beyond the end of D. Increase 100 its size (and allocation if necessary). */ 101 dsize++; 102 if (UNLIKELY (d->_mp_alloc < dsize)) 103 dp = _mpz_realloc (d, dsize); 104 105 dp[i] = 1; 106 d->_mp_size = -dsize; 107 fin:; 108 } 109 } 110 else 111 ; 112 } 113} 114