Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>What you copied is a template for generating code. It's not a good idea to transliterate that template into another language and expect it to run fast. Let's expand the template.</p> <p>(T)~(T)0 means "as many 1-bits as fit in type T". The algorithm needs 4 masks which we will compute for the various T-sizes we might be interested in.</p> <pre><code>&gt;&gt;&gt; for N in (8, 16, 32, 64, 128): ... all_ones = (1 &lt;&lt; N) - 1 ... constants = ' '.join([hex(x) for x in [ ... all_ones // 3, ... all_ones // 15 * 3, ... all_ones // 255 * 15, ... all_ones // 255, ... ]]) ... print N, constants ... 8 0x55 0x33 0xf 0x1 16 0x5555 0x3333 0xf0f 0x101 32 0x55555555L 0x33333333L 0xf0f0f0fL 0x1010101L 64 0x5555555555555555L 0x3333333333333333L 0xf0f0f0f0f0f0f0fL 0x101010101010101L 128 0x55555555555555555555555555555555L 0x33333333333333333333333333333333L 0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0fL 0x1010101010101010101010101010101L &gt;&gt;&gt; </code></pre> <p>You'll notice that the masks generated for the 32-bit case match those in the hardcoded 32-bit C code. Implementation detail: lose the <code>L</code> suffix from the 32-bit masks (Python 2.x) and lose all <code>L</code> suffixes for Python 3.x.</p> <p>As you can see the whole template and (T)~(T)0 caper is merely obfuscatory sophistry. Put quite simply, for a k-byte type, you need 4 masks:</p> <pre><code>k bytes each 0x55 k bytes each 0x33 k bytes each 0x0f k bytes each 0x01 </code></pre> <p>and the final shift is merely N-8 (i.e. 8*(k-1)) bits. Aside: I doubt if the template code would actually work on a machine whose CHAR_BIT was not 8, but there aren't very many of those around these days.</p> <p>Update: There is another point that affects the correctness and the speed when transliterating such algorithms from C to Python. The C algorithms often assume unsigned integers. In C, operations on unsigned integers work silently modulo 2**N. In other words, only the least significant N bits are retained. No overflow exceptions. Many bit twiddling algorithms rely on this. However (a) Python's <code>int</code> and <code>long</code> are signed (b) old Python 2.X will raise an exception, recent Python 2.Xs will silently promote <code>int</code> to <code>long</code> and Python 3.x <code>int</code> == Python 2.x <code>long</code>.</p> <p>The correctness problem usually requires <code>register &amp;= all_ones</code> at least once in the Python code. Careful analysis is often required to determine the minimal correct masking.</p> <p>Working in <code>long</code> instead of <code>int</code> doesn't do much for efficiency. You'll notice that the algorithm for 32 bits will return a <code>long</code> answer even from input of <code>0</code>, because the 32-bits all_ones is <code>long</code>.</p>
    singulars
    1. This table or related slice is empty.
    1. POPython equivalent of C code from Bit Twiddling Hacks?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJohn Machin
    1. USJohn Machin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload