'''simple docstring'''
from timeit import timeit







def        A_     (						__SCREAMING_SNAKE_CASE						:  int )				->       int:





  """simple docstring"""

  if number < 0:
    raise ValueError("""the value of input must not be negative""" )
  __A		:     Optional[int]												=		0
  while number:
    number &= number - 1
    result += 1
  return result







def        A_     (						__SCREAMING_SNAKE_CASE						:  int )				->       int:





  """simple docstring"""

  if number < 0:
    raise ValueError("""the value of input must not be negative""" )
  __A		:     Any												=		0
  while number:
    if number % 2 == 1:
      result += 1
    number >>= 1
  return result







def        A_     (						)				->       None:





  """simple docstring"""

  def do_benchmark(__SCREAMING_SNAKE_CASE						:  int ) -> None:
    __A		:     Any												=		"""import __main__ as z"""
    print(F"Benchmark when {number = }:" )
    print(F"{get_set_bits_count_using_modulo_operator(__SCREAMING_SNAKE_CASE ) = }" )
    __A		:     Optional[int]												=		timeit("""z.get_set_bits_count_using_modulo_operator(25)"""			,     setup=__SCREAMING_SNAKE_CASE )
    print(F"timeit() runs in {timing} seconds" )
    print(F"{get_set_bits_count_using_brian_kernighans_algorithm(__SCREAMING_SNAKE_CASE ) = }" )
    __A		:     Optional[Any]												=		timeit(
        """z.get_set_bits_count_using_brian_kernighans_algorithm(25)"""			,     setup=__SCREAMING_SNAKE_CASE			,     )
    print(F"timeit() runs in {timing} seconds" )

  for number in (25, 37, 58, 0):
    do_benchmark(__SCREAMING_SNAKE_CASE )
    print()


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     benchmark()





'''simple docstring'''
def        A_     (						__SCREAMING_SNAKE_CASE						:  int			,     __SCREAMING_SNAKE_CASE						:  bool = False )				->       bool:





  """simple docstring"""

  if n == 2:
    return True
  if not n % 2 or n < 2:
    return False
  if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
    return False
  if n > 3_3170_4406_4679_8873_8596_1981 and not allow_probable:
    raise ValueError(
        """Warning: upper bound of deterministic test is exceeded. """
        """Pass allow_probable=True to allow probabilistic test. """
        """A return value of True indicates a probable prime.""" )
  # array bounds provided by analysis
  __A		:     Optional[int]												=		[
      2047,
      137_3653,
      2532_6001,
      32_1503_1751,
      2_1523_0289_8747,
      3_4747_4966_0383,
      341_5500_7172_8321,
      1,
      382_5123_0565_4641_3051,
      1,
      1,
      3186_6585_7834_0311_5116_7461,
      3_3170_4406_4679_8873_8596_1981,
  ]

  __A		:     Optional[int]												=		[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
  for idx, _p in enumerate(__SCREAMING_SNAKE_CASE			,     1 ):
    if n < _p:
      # then we have our last prime to check
      __A		:     Union[str, Any]												=		primes[:idx]
      break
  __A							,					__A		:     int												=		n - 1, 0
  # break up n -1 into a power of 2 (s) and
  # remaining odd component
  # essentially, solve for d * 2 ** s == n - 1
  while d % 2 == 0:
    d //= 2
    s += 1
  for prime in plist:
    __A		:     int												=		False
    for r in range(__SCREAMING_SNAKE_CASE ):
      __A		:     Optional[Any]												=		pow(__SCREAMING_SNAKE_CASE			,     d * 2**r			,     __SCREAMING_SNAKE_CASE )
      # see article for analysis explanation for m
      if (r == 0 and m == 1) or ((m + 1) % n == 0):
        __A		:     Optional[int]												=		True
        # this loop will not determine compositeness
        break
    if pr:
      continue
    # if pr is False, then the above loop never evaluated to true,
    # and the n MUST be composite
    return False
  return True







def        A_     (						)				->       None:





  """simple docstring"""

  assert not miller_rabin(561 )
  assert miller_rabin(563 )
  # 2047

  assert not miller_rabin(83_8201 )
  assert miller_rabin(83_8207 )
  # 1_373_653

  assert not miller_rabin(1731_6001 )
  assert miller_rabin(1731_6017 )
  # 25_326_001

  assert not miller_rabin(30_7838_6641 )
  assert miller_rabin(30_7838_6653 )
  # 3_215_031_751

  assert not miller_rabin(1_7130_4557_4801 )
  assert miller_rabin(1_7130_4557_4819 )
  # 2_152_302_898_747

  assert not miller_rabin(2_7797_9972_8307 )
  assert miller_rabin(2_7797_9972_8327 )
  # 3_474_749_660_383

  assert not miller_rabin(113_8500_2390_9441 )
  assert miller_rabin(113_8500_2390_9527 )
  # 341_550_071_728_321

  assert not miller_rabin(127_5041_0188_4880_4351 )
  assert miller_rabin(127_5041_0188_4880_4391 )
  # 3_825_123_056_546_413_051

  assert not miller_rabin(796_6646_4458_5077_8779_1867 )
  assert miller_rabin(796_6646_4458_5077_8779_1951 )
  # 318_665_857_834_031_151_167_461

  assert not miller_rabin(5528_4067_7446_6478_9766_0333 )
  assert miller_rabin(5528_4067_7446_6478_9766_0359 )
  # 3_317_044_064_679_887_385_961_981
  # upper limit for probabilistic test


if __name__ == "__main__":
     test_miller_rabin()



