[GHC] #14818: Provide highestOneBit function in Data.Bits module
#14818: Provide highestOneBit function in Data.Bits module -------------------------------------+------------------------------------- Reporter: kostmo | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: Component: | Version: 8.2.2 libraries/base | Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- This function yields the [https://stackoverflow.com/a/17379704/105137 largest power of 2 less than or equal to the given number]. Relative to the Java standard library, which [https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#highestOneB...) provides this function], there is a gap in the Haskell library, even though the Haskell docs [https://hackage.haskell.org/package/base-4.10.1.0/docs/Data- Bits.html#v:countLeadingZeros describe a method to calculate logBase2 via the `countLeadingZeros` function]. From the Java documentation:
The implementations of the "bit twiddling" methods (such as `highestOneBit` and `numberOfTrailingZeros`) are based on material from Henry S. Warren, Jr.'s ''Hacker's Delight'', (Addison Wesley, 2002).
-- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14818 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14818: Provide highestOneBit function in Data.Bits module -------------------------------------+------------------------------------- Reporter: kostmo | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): JFTR: The `containers` library needs this function, and defines it in its `Utils` module: http://hackage.haskell.org/package/containers-0.5.11.0/docs/Utils- Containers-Internal-BitUtil.html: {{{ -- The highestBitMask implementation is based on -- http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 -- which has been put in the public domain. -- | Return a word where only the highest bit is set. highestBitMask :: Word -> Word highestBitMask x1 = let x2 = x1 .|. x1 `shiftRL` 1 x3 = x2 .|. x2 `shiftRL` 2 x4 = x3 .|. x3 `shiftRL` 4 x5 = x4 .|. x4 `shiftRL` 8 x6 = x5 .|. x5 `shiftRL` 16 #if !(defined(__GLASGOW_HASKELL__) && WORD_SIZE_IN_BITS==32) x7 = x6 .|. x6 `shiftRL` 32 in x7 `xor` (x7 `shiftRL` 1) #else in x6 `xor` (x6 `shiftRL` 1) #endif {-# INLINE highestBitMask #-} }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14818#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14818: Provide highestOneBit function in Data.Bits module -------------------------------------+------------------------------------- Reporter: kostmo | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): If I understand correctly, we already have these: * `countLeadingZeros` is `GHC.Prim.clzN#`, which is exposed by `Data.Bits.countLeadingZeros`. * `highestOneBit` is `GHC.Prim.ctzN#`, which is exposed by `Data.Bits.countTrailingZeros` -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14818#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14818: Provide highestOneBit function in Data.Bits module -------------------------------------+------------------------------------- Reporter: kostmo | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: 7.10.1 Component: libraries/base | Version: 8.2.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => closed * resolution: => fixed * milestone: => 7.10.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14818#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14818: Provide highestOneBit function in Data.Bits module -------------------------------------+------------------------------------- Reporter: kostmo | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: closed => new * cc: core-libraries-committee@… (added) * resolution: fixed => * milestone: 7.10.1 => Comment: Whoops, my apologies; I clearly misunderstood the description. I see now that you are actually proposing a new addition to `Data.Bits`. I think it would be best if this request went through the [[https://wiki.haskell.org/Core_Libraries_Committee|core libraries process]]. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14818#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14818: Provide highestOneBit function in Data.Bits module -------------------------------------+------------------------------------- Reporter: kostmo | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #4102 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * related: => #4102 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14818#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC