NaN is not one bit pattern: sorting floats by integer keys
float("nan") and 0/0 both print as nan, but they are not always the same bits. A sort that never compares the floats, and instead ranks an integer key made from those bits, can give those NaNs a rank against each other. That breaks a stable rule: equal values keep the earlier column. Fold every NaN to one bit pattern before the key is built.
bits --> key --> radix / sort --> top-k
|
+-- more than one NaN pattern
--> more than one key
--> NaNs get a rank
--> a stable tie breaks
fix: one pattern for every NaN, then the keyThe listing below is the output of one toy, run with CPython 3.12.4 and NumPy 2.0.1. NumPy is the only dependency.
python3 001-nan-sort-key-toy.py1. The bits of a float32, and what a NaN is
fp32 = [ sign 1 ][ exponent 8 ][ mantissa 23 ]
exponent == 11111111, mantissa == 0 -> ±inf
exponent == 11111111, mantissa != 0 -> NaN
first mantissa bit 1 -> quiet NaN (qNaN)
first mantissa bit 0 -> signaling NaN (sNaN)
the other mantissa bits -> payload=== 1. fp32 = sign | exponent (8) | mantissa (23)
name | hex | sign | exponent | mantissa | isnan
1.0 | 0x3f800000 | 0 | 01111111 | 00000000000000000000000 | False
+inf | 0x7f800000 | 0 | 11111111 | 00000000000000000000000 | False
+qNaN | 0x7fc00000 | 0 | 11111111 | 10000000000000000000000 | True
-qNaN | 0xffc00000 | 1 | 11111111 | 10000000000000000000000 | True
+NaN payload 1 | 0x7fc00001 | 0 | 11111111 | 10000000000000000000001 | True
+sNaN | 0x7f800001 | 0 | 11111111 | 00000000000000000000001 | Trueisnan is true for all four NaNs. A NaN is not one value. It is a set of about 224 bit patterns.
2. Which operation writes which NaN
=== 2. which bits an operation produces (this CPU)
operation | hex | printed
float('nan') | 0x7fc00000 | nan
0 / 0 | 0x7fc00000 | nan
inf - inf | 0x7fc00000 | nan
0 * inf | 0x7fc00000 | nan
sqrt(-1) | 0x7fc00000 | nan
-float('nan') | 0xffc00000 | nanOn this run, invalid operations wrote the same quiet NaN as float("nan"). Negation flipped only the sign bit, so -float("nan") is 0xffc00000. The same script on another CPU printed 0xffc00000 for 0/0, inf-inf, 0*inf, and sqrt(-1). Both results are allowed. The hardware default NaN is not portable, and every line above still prints as nan.
| Source | Bits you should expect | Note |
|---|---|---|
float("nan"), np.nan | +qNaN 0x7fc00000 | A NaN written as a constant |
0/0, inf-inf, 0*inf | The hardware default NaN | This run: 0x7fc00000. Another CPU: 0xffc00000 |
-x | The sign bit flips | True for a NaN as well as for a number |
| A NaN with another payload | Uncommon | Built by writing the bits, or passed through by some operations |
A row can hold a constant NaN and a computed NaN at once. Printed, they look the same.
3. Comparisons do not rank a NaN
=== 3. NaN compares false to everything, itself included
+qNaN == +qNaN : False
+qNaN == -qNaN : False
+qNaN > 1.0 : False
+qNaN < 1.0 : FalseThe sort has to choose a rule. A common one is: every NaN ranks above +inf, and every NaN ties with every other NaN. Under a stable sort, the column order then decides among NaNs.
4. An unsigned key whose order matches the float
A radix sort does not compare values. It builds a key from the bits and buckets by the key's digits. A usual conversion:
| Input | Conversion | Why |
|---|---|---|
| sign = 0 (positive) | Set the sign bit | Positives sort above negatives |
| sign = 1 (negative) | Flip every bit | A larger magnitude becomes a smaller key |
=== 4. a float as an unsigned key whose order is the float order
value | bits | raw key | canonical key
-qNaN | 0xffc00000 | 0x003fffff | 0xffc00000
-inf | 0xff800000 | 0x007fffff | 0x007fffff
-1.0 | 0xbf800000 | 0x407fffff | 0x407fffff
-0.0 | 0x80000000 | 0x7fffffff | 0x7fffffff
+0.0 | 0x00000000 | 0x80000000 | 0x80000000
1.0 | 0x3f800000 | 0xbf800000 | 0xbf800000
+inf | 0x7f800000 | 0xff800000 | 0xff800000
+qNaN | 0x7fc00000 | 0xffc00000 | 0xffc00000
+NaN payload 1 | 0x7fc00001 | 0xffc00001 | 0xffc00000where the NaNs sit in raw-key order
0x003fffff 0x007fffff ... 0xff800000 0xffc00000 0xffc00001
-qNaN -inf ... +inf +qNaN +NaN payload 1
^ below -inf ^ above +inf, and one key per payloadFor every non-NaN, key order matches float order. For NaNs it does not. -qNaN sorts below -inf, +qNaN sorts above +inf, and a different payload is a different key. The canonical key column is what you get after every NaN has been rewritten to +qNaN first. Those NaNs share one key.
5. What that does to a stable top-k
Width 8, k = 2, and the rule from section 3: NaNs sit above +inf, and NaNs tie with each other.
| Key | NaNs versus +inf | NaNs versus each other |
|---|---|---|
| raw | Above +inf, but the raw key is kept | Each bit pattern has its own rank |
| canonical | One key, above +inf | A tie, so the column decides |
=== 5. stable top-k: largest key first, equal keys -> smaller column first
column | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
row A | +qNaN | +qNaN | -qNaN | -qNaN | 3.0 | inf | 1.0 | -2.0
row B | +qNaN | +qNaN | +NaN p1 | +NaN p1 | 3.0 | inf | 1.0 | -2.0
row C | -qNaN | -qNaN | +qNaN | +qNaN | 3.0 | inf | 1.0 | -2.0
want | NaN above +inf, all NaNs equal -> top-2 = columns [0, 1] in every row
row | key | top-2 | verdict
A | raw | [0, 1] | right
A | canonical | [0, 1] | right
B | raw | [2, 3] | WRONG: the later NaNs outrank the earlier ones
B | canonical | [0, 1] | right
C | raw | [2, 3] | WRONG: the later NaNs outrank the earlier ones
C | canonical | [0, 1] | rightRow A happens to be right: the earlier columns are the NaNs with the higher raw key. Rows B and C are wrong: a later NaN outranks an earlier one. After canonicalizing, all four NaNs tie, so columns 0 and 1 win on every row.
| The bug shows up only when | Why it stays hidden otherwise |
|---|---|
| The sort promises stability (an earlier column wins a tie) | An unstable sort may return any of the NaNs |
| There are more NaNs than k | With k or fewer, every NaN is selected, so their order never appears |
| The NaNs mix signs or payloads | One pattern means one key, so they tie |
The last row is why a test that "includes some NaNs" misses this. A handful of float("nan") values, all the same pattern, pass.
6. Canonicalize before the key
bits -- is it a NaN? (bits & 0x7fffffff) > 0x7f800000
yes -> bits = 0x7fc00000 every NaN, one pattern
no -> keep the bits
-> then the key conversion from section 4- Each element gains one compare and one select. When the sort is limited by reading memory, that cost is often invisible. Do not claim that until you time it.
- If more than one place builds a key (a select stage and an output stage, for example), every place must canonicalize the same way. One side left raw will disagree with the other about order.
- Which pattern you pick does not matter. What matters is that every NaN becomes the same key.
- The test is the condition in section 5: stable, more NaNs than k, mixed signs and payloads, and a layout where the higher raw key sits in a later column (rows B and C).
Terms
| Term | Meaning |
|---|---|
| NaN | A float whose exponent is all ones and whose mantissa is not zero. Every comparison is false |
| qNaN / sNaN | Quiet if the first mantissa bit is 1, signaling if it is 0. Arithmetic almost always produces a qNaN |
| payload | The remaining mantissa bits. They are not a numeric value |
| default NaN | The NaN an invalid operation such as 0/0 returns. Its bits depend on the hardware |
| sort key | The bits rewritten so that an integer compare reproduces float order |
| canonicalize | Folding several representations of one meaning into one. Here, every NaN becomes 0x7fc00000 |
| stable | Equal keys keep their original order. Here, that order is the column order |
| top-k | The operation that selects the positions of the k largest values |
Sections 1 and 3–5 were run with CPython 3.12.4 and NumPy 2.0.1 and match the listing. Section 2 is that same run; another CPU printed a negative default NaN for the invalid operations.