On Wed, 17 Oct 2007 23:06:24 -0700, Ixiaus wrote: > I know '<<' is shifting x over by n bits; but could you point me to some > literature that would explain why it is the same as "x*2**n"? (Googling > only returns bit shift, but doesn't necessarily explain the manner in > which you are using it)
In decimal, multiplying by ten shifts the digits to the left by one place: 31 * 10 => 310 310 * 10 => 3100 3100 * 10 => 31000 In binary, multiplying by two shifts the bits to the left by one place: 101 * 10 => 1010 1010 * 10 => 10100 10100 * 10 => 101000 Because the underlying numbers are the same regardless of what base we use to write it in, bit-shifts to the left are equivalent to repeated multiplication by two regardless of the display base. Hence: >>> 7 << 1 14 >>> 14 << 1 28 >>> 28 << 1 56 or to do it another way: >>> 7 << 3 # multiplication by 2**3 56 Similarly, a bit-shift to the right is equivalent to dividing by two and dropping any remainder. > I will have to read up more on Generators, but maybe you can give me a > lowdown on why > sum([1 << k for k, i in enumerate(reversed(val)) if int(i)]) is less > efficient than using a Generator (is the generator a 'temporary' list?) > sum(1 << k for k, i in enumerate(reversed(val)) if int(i)) The list comprehension: [1 << k for k, i in enumerate(reversed(val)) if int(i)] creates the entire list first. That potentially can require a lot of memory, leading to all sorts of complicated memory shuffles as the list is resized, paging, etc. Using a generator expression means that you avoid creating the entire list all in one go. That saves you memory, which may mean that you save time. However, for small sets of input, it is likely that the overhead of creating the generator in the first place outweighs the saving of not creating the whole list. The definition of "small" depends on what you are trying to do. In my tests, I have found that sum(list comprehension) is marginally faster than sum(generator expression) even for 10,000 items. -- Steven -- http://mail.python.org/mailman/listinfo/python-list