{-# OPTIONS_HADDOCK hide #-}

-- | Bit operations not in the `Data.Bits` module.
--
-- ==== __Example__
-- >>> bitCeil 0
-- 1
--
-- >>> bitCeil 1
-- 1
--
-- >>> bitCeil 2
-- 2
--
-- >>> bitCeil 3
-- 4
--
-- >>> bitCeil 4
-- 4
--
-- @since 1.0.0.0
module AtCoder.Internal.Bit
  ( -- * Utilities
    bitCeil,
  )
where

-- TODO: faster implmentation

-- | \(O(w)\) Returns minimum \(2^i s.t. 2^i \geq n\).
--
-- @since 1.0.0.0
{-# INLINE bitCeil #-}
bitCeil :: Int -> Int
bitCeil :: Int -> Int
bitCeil Int
n = Int -> Int
inner Int
1
  where
    inner :: Int -> Int
inner Int
x
      | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = Int
x
      | Bool
otherwise = Int -> Int
inner (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
x

-- countTrailingZeros from Data.Bits