2012-11-29-Solution-to-yesterday-s-quiz.html

---
layout: post
author: Pascal Cuoq
date: 2012-11-29 23:02 +0200
categories: anonymous-arrays c99 floating-point
format: xhtml
title: "Solution to yesterday's quiz"
summary: 
---
{% raw %}
<p>Yesterday's quiz was about the expression <code>*(char*)(float[]){x*x} - 63</code> (for big-endian architectures) or <code>*(3+(char*)(float[]){x*x}) - 63</code> (for little-endian ones). This post provides an explanation.</p> 
<p>First, let us try the function on a few values:</p> 
<pre>int main(){ 
  for (unsigned int i=0; i&lt;=20; i++) 
    printf(\l(%2u)=%d"  i  l(i)); 
} 
</pre> 
<p>This may provide the beginning of a hint:</p> 
<pre>l( 0)=-63 
l( 1)=0 
l( 2)=1 
l( 3)=2 
l( 4)=2 
l( 5)=2 
l( 6)=3 
l( 7)=3 
l( 8)=3 
l( 9)=3 
l(10)=3 
l(11)=3 
l(12)=4 
l(13)=4 
l(14)=4 
l(15)=4 
l(16)=4 
l(17)=4 
l(18)=4 
l(19)=4 
l(20)=4 
</pre> 
<p>The construct <code>(float[]){…}</code> is C99's syntax for anonymous arrays  a kickass programming technique. This is an unabated quote.</p> 
<p>In the case at hand  the construct converts to float the contents of the braces and puts the result in memory. The function puts the float in memory in order to read its most significant byte. That's <code>*(char*)…</code> on a big-endian architecture  and <code>*(3+(char*)…)</code> on a little-endian one.</p> 
<p>One reason to read a single char is to circumvent <a href="http://stackoverflow.com/q/98650/139746">strict aliasing rules</a>—which do not apply to type <code>char</code>. A simpler version of the same function would have been <code>(*(int*)(float[]){x} &gt;&gt; 23) - 127</code>  but that version would break strict aliasing rules. Also  it would be too obvious.</p> 
<p>The most significant bits of a single-precision IEEE 754 floating-point representation are  in order  one sign bit and eight exponent bits. By reading the most significant byte  we get most of the exponent  but one bit is lost. To compensate for this  the operation is applied to <code>x*x</code>  whose exponent is double the exponent of <code>x</code>.</p> 
<p>In conclusion  yesterday's one-liner returns an integer approximation of the base-2 logarithm of a reasonably small <code>unsigned int x</code>. On a typical 32-bit architecture  it is exact for powers of two up to <code>2¹⁵</code>. If <code>x</code> is zero  the function returns its best approximation of <code>-∞</code>  that is  <code>-63</code>.</p>
{% endraw %}