2's Compliment Solution (InterviewStreet CodeSprint Fall 2011)

bitcount.rb

class Numeric
  def find_last_bit
    r = 0
    n = self
    32.times do
      n >>= 1
      break if n==0
      r = r+1
    end
    return r
  end

end

$hash_for_bit_set = [1]

def num_bits_set mthbit
  n = (1 << mthbit)
  if n > 0
    if n == 1      
      return 1
    else
      return $hash_for_bit_set[mthbit] if $hash_for_bit_set[mthbit]
      val = (n/2) + (num_bits_set((n/2).find_last_bit) -1 )*2  +1
      $hash_for_bit_set[mthbit] = val
      return val        
    end
  end
  
end

def num_bits_set_in_seq num
  return 0 if num == 0
  num_bits = {}
  n = num
  val = 0
  count = 0
  while n != 0
    val += $hash_for_bit_set[n.find_last_bit]
    count = count + 1
    n = (n & ~(1 << n.find_last_bit))
    val = val + count * ((1 << n.find_last_bit)) if n != 0
  end
  return val 
end


numcases = []
STDIN.readline.to_i.times do 
  numcases << STDIN.readline.split(' ').map { |m| m.to_i } 
end

ans = []
num_bits_set 31
num_bit_in_neg = num_bits_set_in_seq(0xFFFFFFFF)

countcase = 0
numcases.each do |m|

  countcase = countcase + 1
  total1 = 0 
  total2 = 0
  if m[0] < 0
    total1 = num_bit_in_neg - num_bits_set_in_seq(0xFFFFFFFF + m[0])  if m[0] != -1

    total1 = 32 if m[0] == -1
  end

  if m[1] < 0
    total2 = num_bit_in_neg - num_bits_set_in_seq(0xFFFFFFFF + m[1]+1)  if m[1] != -1
    total2 = 0 if m[1] == -1
  end

  if (m[0] < 0 and m[1] < 0)
    total = total1 - total2
  end

  if (m[0] < 0 and m[1] >= 0)
    total = total1 + num_bits_set_in_seq(m[1])
  end

  if ((m[0] >= 0) and (m[1] >= 0 ))
    total = num_bits_set_in_seq(m[1]) - num_bits_set_in_seq(m[0]-1) if m[0] != 0
    total = num_bits_set_in_seq(m[1]) if m[0] == 0
  end    

  ans << total 
end

puts ans