scan1.c
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:4k
源码类别:

数学计算

开发平台:

Unix_Linux

  1. /* mpz_scan1 -- search for a 1 bit.
  2. Copyright 2000, 2001, 2002, 2004 Free Software Foundation, Inc.
  3. This file is part of the GNU MP Library.
  4. The GNU MP Library is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU Lesser General Public License as published by
  6. the Free Software Foundation; either version 3 of the License, or (at your
  7. option) any later version.
  8. The GNU MP Library is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  11. License for more details.
  12. You should have received a copy of the GNU Lesser General Public License
  13. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  14. #include "gmp.h"
  15. #include "gmp-impl.h"
  16. #include "longlong.h"
  17. /* mpn_scan0 can't be used for the inverted u<0 search since there might not
  18.    be a 0 bit before the end of the data.  mpn_scan1 could be used under u>0
  19.    (except when in the high limb), but usually the search won't go very far
  20.    so it seems reasonable to inline that code.  */
  21. mp_bitcnt_t
  22. mpz_scan1 (mpz_srcptr u, mp_bitcnt_t starting_bit)
  23. {
  24.   mp_srcptr      u_ptr = PTR(u);
  25.   mp_size_t      size = SIZ(u);
  26.   mp_size_t      abs_size = ABS(size);
  27.   mp_srcptr      u_end = u_ptr + abs_size;
  28.   mp_size_t      starting_limb = starting_bit / GMP_NUMB_BITS;
  29.   mp_srcptr      p = u_ptr + starting_limb;
  30.   mp_limb_t      limb;
  31.   int            cnt;
  32.   /* Past the end there's no 1 bits for u>=0, or an immediate 1 bit for u<0.
  33.      Notice this test picks up any u==0 too. */
  34.   if (starting_limb >= abs_size)
  35.     return (size >= 0 ? ULONG_MAX : starting_bit);
  36.   limb = *p;
  37.   if (size >= 0)
  38.     {
  39.       /* Mask to 0 all bits before starting_bit, thus ignoring them. */
  40.       limb &= (MP_LIMB_T_MAX << (starting_bit % GMP_NUMB_BITS));
  41.       if (limb == 0)
  42.         {
  43.           /* If it's the high limb which is zero after masking, then there's
  44.              no 1 bits after starting_bit.  */
  45.           p++;
  46.           if (p == u_end)
  47.             return ULONG_MAX;
  48.           /* Otherwise search further for a non-zero limb.  The high limb is
  49.              non-zero, if nothing else.  */
  50.           for (;;)
  51.             {
  52.               limb = *p;
  53.               if (limb != 0)
  54.                 break;
  55.               p++;
  56.               ASSERT (p < u_end);
  57.             }
  58.         }
  59.     }
  60.   else
  61.     {
  62.       mp_srcptr  q;
  63.       /* If there's a non-zero limb before ours then we're in the ones
  64.          complement region.  Search from *(p-1) downwards since that might
  65.          give better cache locality, and since a non-zero in the middle of a
  66.          number is perhaps a touch more likely than at the end.  */
  67.       q = p;
  68.       while (q != u_ptr)
  69.         {
  70.           q--;
  71.           if (*q != 0)
  72.             goto inverted;
  73.         }
  74.       if (limb == 0)
  75.         {
  76.           /* Skip zero limbs, to find the start of twos complement.  The
  77.              high limb is non-zero, if nothing else.  This search is
  78.              necessary so the -limb is applied at the right spot. */
  79.           do
  80.             {
  81.               p++;
  82.               ASSERT (p < u_end);
  83.               limb = *p;
  84.             }
  85.           while (limb == 0);
  86.           /* Apply twos complement, and look for a 1 bit in that.  Since
  87.              limb!=0 here, also have (-limb)!=0 so there's certainly a 1
  88.              bit.  */
  89.           limb = -limb;
  90.           goto got_limb;
  91.         }
  92.       /* Adjust so ~limb implied by searching for 0 bit becomes -limb.  */
  93.       limb--;
  94.     inverted:
  95.       /* Now seeking a 0 bit. */
  96.       /* Mask to 1 all bits before starting_bit, thus ignoring them. */
  97.       limb |= (CNST_LIMB(1) << (starting_bit % GMP_NUMB_BITS)) - 1;
  98.       /* Search for a limb which is not all ones.  If the end is reached
  99.          then the zero immediately past the end is the result.  */
  100.       while (limb == GMP_NUMB_MAX)
  101.         {
  102.           p++;
  103.           if (p == u_end)
  104.             return (mp_bitcnt_t) abs_size * GMP_NUMB_BITS;
  105.           limb = *p;
  106.         }
  107.       /* Now seeking low 1 bit. */
  108.       limb = ~limb;
  109.     }
  110.  got_limb:
  111.   ASSERT (limb != 0);
  112.   count_trailing_zeros (cnt, limb);
  113.   return (mp_bitcnt_t) (p - u_ptr) * GMP_NUMB_BITS + cnt;
  114. }