1 /* mpz_hamdist -- calculate hamming distance.
3 Copyright 1994, 1996, 2001, 2002, 2009, 2010, 2011 Free Software Foundation,
6 This file is part of the GNU MP Library.
8 The GNU MP Library is free software; you can redistribute it and/or modify
9 it under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or (at your
11 option) any later version.
13 The GNU MP Library is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16 License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
26 mpz_hamdist (mpz_srcptr u, mpz_srcptr v) __GMP_NOTHROW
29 mp_size_t usize, vsize;
41 return ~ (mp_bitcnt_t) 0;
43 /* positive/positive */
46 MPN_SRCPTR_SWAP (up,usize, vp,vsize);
50 count = mpn_hamdist (up, vp, vsize);
54 count += mpn_popcount (up + vsize, usize);
60 mp_limb_t ulimb, vlimb;
61 mp_size_t old_vsize, step;
64 return ~ (mp_bitcnt_t) 0;
66 /* negative/negative */
71 /* skip common low zeros */
88 MPN_SRCPTR_SWAP (up,usize, vp,vsize);
95 /* twos complement first non-zero limbs (ulimb is non-zero, but vlimb
99 popc_limb (count, (ulimb ^ vlimb) & GMP_NUMB_MASK);
103 mp_bitcnt_t twoscount;
105 /* first non-zero of v */
115 /* part of u corresponding to skipped v zeros */
116 step = old_vsize - vsize - 1;
117 count += step * GMP_NUMB_BITS;
118 step = MIN (step, usize);
121 count -= mpn_popcount (up, step);
126 /* First non-zero vlimb as twos complement, xor with ones
127 complement ulimb. Note -v^(~0^u) == (v-1)^u. */
134 popc_limb (twoscount, vlimb);
138 /* Overlapping part of u and v, if any. Ones complement both, so just
140 step = MIN (usize, vsize);
143 count += mpn_hamdist (up, vp, step);
150 /* Remaining high part of u or v, if any, ones complement but xor
151 against all ones in the other, so plain popcount. */
155 count += mpn_popcount (up, usize);