CODEWITHSUNDEEP
haskellbit-manipulation
jorgbrown
jorgbrown

Reputation: 2051

how to do bit shifts and masks in haskell?

I'm writing a routine to determine whether the high 16 bits of a 32-bit integer have more bits set, or the low bits.

In C, I would write this:

bool more_high_bits(int a) {
  if ((a >> 16) == 0) return false;    // no high bits
  if ((a & 0xFFFF) == 0) return true;  // no low bits

  // clear one high bit and one low bit, and ask again
  return more_high_bits(a&(a - 0x10001));
}

So in Haskell, I'm trying this:

more_high_bits a=if (a `shiftR` 16) /= 0 then 0 else
                 if ((.&.) a 65535) /= 0 then 1 else
                 more_high_bits((.&.) a (a-65537))

But it just times out.

What am I doing wrong? What's the more idiomatic way to do this? Please don't code away the shift or the & because I'd like to know how I "should" be using these.

Addendum: I tried this code out on an haskell compiler:

http://www.tutorialspoint.com/compile_haskell_online.php

import Data.Bits

g a=if (a `shiftR` 16) == 0 then 0 else
    if ((.&.) a 65535) == 0 then 1 else
    g((.&.) a (a-65537))

main = print (g(237))

But it tells me "No instance for (Bits a0) arising from a use of 'g' The type variable 'a0' is ambiguous"

What is "a0"??

Upvotes: 5

Views: 7485

Answers (1)

melpomene
melpomene

Reputation: 85767

Here's a pretty direct translation of your C code to Haskell:

import Data.Word
import Data.Bits

more_high_bits :: Word32 -> Bool
more_high_bits a
    | (a `shiftR` 16) == 0 = False
    | (a .&. 0xFFFF)  == 0 = True
    | otherwise            = more_high_bits (a .&. (a - 0x10001))

Your attempt has /= where the C version has ==, which inverts the condition.

a0 is the type variable that the type checker automatically created for your use of g 237. It doesn't know which type you mean because 237 could be any numeric type at all, and g works with all numbers that support bitwise operations and equality. The list of types you could have meant includes (but is not limited to) Int, Integer, Word, ...

Upvotes: 9

Related Questions