I'll stick my neck out here and explain my guess about what Erik is suggesting. If my guess is correct, the trick is to stop thinking about searching the space containing billions and billions of addresses and instead think about searching through the much less daunting space that contains 48 address bits.

Here's one way to do that. First make the following assumptions:

• Each slave has a unique 48-bit address.
• At each enumeration step, the master sends out two 48-bit strings. One of these is a test address. The other is a mask that tells the slaves which of the test address bits to consider during the current enumeration step. Let's say that a '1' bit in the mask means that the slave should consider the corresponding bit in the test address, and that a '0' bit in the mask means that the slave should ignore the corresponding bit in the test address.
• When a slave receives an address/mask pair, it immediately compares the test address sent by the master with its own address, but considering only the address bits corresponding to '1' bits in the current mask. If there is a match and the slave has not already been identified by the master, then the slave transmits its entire address. Otherwise, it remains silent.
• After the master sends an address/mask pair, it listens for the slaves' responses. The master can distinguish among these possibilities:
  1. No slaves respond
  2. Exactly one slave responds
  3. More than one slave responds

Now consider the following diagram, which represents the slave addresses. I've drawn it as though though the addresses were only 3 bits wide. (If you want to draw the diagram for 48-bit addresses, go ahead!)

The master starts the enumeration process by commanding all the slaves to mark themselves as not yet having been identified.

The master then traverses the address tree in left-first order, starting at the top node. At each node, the master creates the test address by replacing the each X shown for that node with a 0 or a 1 (it doesn't matter which). It creates the mask by placing a 1 in each position where a 1 or 0 is shown in the diagram, and a 0 in each position where an X appears in the diagram.

Then, after sending the address/mask pair and receiving the slaves' responses, the master behaves as follows:

• If a single slave responds, that means that it is the only slave having an address within the subtree whose root is at the current node. In this case, the master records that slave's address and commands the slave to mark itself as having been identified. The master then abandons the search of that subtree and continues the tree traversal as though the subtree had been traversed.
• If no slaves respond, that means that no slave has an address within the subtree whose root is at the current node. In this case, the master abandons the search of that subtree and continues the tree traversal as though the subtree had been traversed.
• If multiple slaves respond, that means that multiple slaves have addresses within the subtree whose root is at the current node. In this case, the master continues to traverse the tree normally.

The algorithm ends when the tree traversal is complete. With any reasonable number of slaves, it will be very quick because huge portions of the tree will be pruned as explained above.

See here for the Maxim/Dallas app note that Michael mentioned. It describes a similar scheme for enumerating slaves on a 1-Wire network.

-- Russ