notation - References to these functions relating to binary trees and binary digit counting?

Consider a perfect binary tree with $2^N-1$ elements. Two different numbering methods pop up constantly. For example, for $N=3$:

I have worked out the mapping between these (for $ 1 \le k, i \lt 2^N $, with $i, k, N \in \mathbb{N}$ and $N \ge 2$):
$$i(k, N) = (k - 2^{\lfloor \log_2 k \rfloor}) 2^{N - {\lfloor \log_2 k \rfloor}} + 2^{N - {\lfloor \log_2 k \rfloor} - 1}$$
and
$$k(i, N) = \frac{b(i + 2^N) - 1}{2}$$
where ${\lfloor \log_2 k \rfloor}+1$ is the number of binary digits in $k$, and $b(x)$ is a function that removes the least significant zero binary digits in $x$, or in other words, divides $x$ with the smallest power of two to yield an odd dividend; $x \ge 1 \in \mathbb{N}$.

If we have $1 \le y, n \in \mathbb{N}$, then
$$x = 2^{n-1} \left( 2 y - 1 \right)$$
and we can define $b(x)$ as
$$b(x) = 2 y - 1$$
For illustration,
$$ b(8) = b(0_B1000) = 0_B1 = 1 $$
$$ b(9) = b(0_B1001) = 0_B1001 = 9$$
$$ b(12) = b(0_B1100) = 0_B11 = 3 $$

Questions:

1. Is there a better definition for $b(x)$? Is it a known function?




2. Is $i(k,N)$ a known function? Name or references to articles?




3. Is $k(i,N)$ a known function? Name or references to articles?

Corrections for the notation and nomenclature is also appreciated.

For background and motivation, I've encountered $k(i,N)$ when counting the number of cases (dividends) for which Markstein division acceleration fails, given a specific integer divisor; as well as when packing perfect binary trees into arrays. (I've only seen the latter done using counters or multiple buffers, never via direct computation of the target index $k(i,N)$, which leads me to believe $k(i,N)$ is obscure at least, if not previously unknown.)

---

Adding further background on 2016-03-05:

Sorted data is usually stored in a linear array. This lets an implementation use a binary search to look for a specific value in $O(log_2 N)$ time complexity.

However, if the array is large, cache behaviour is terrible. To look for a specific value, the middle element is looked first, and so on. Given uniformly random searches, the access probability per element looks like the alpine range (or an inverted binary tree, to be more precise).

Binary trees can be stored in an array. If the index of the first element is $1$, element $i$ has a left child at $2 i$ and a right child at $2 i + 1$. If the binary tree is a search tree -- in which the order of the elements increases from left to right, in-order --, the first element in the tree array is the top one. For a perfect tree, this is the middle element, for others, slightly after the middle element.

In binary tree form, cache behaviour is much better. All binary searches (that are actually tree traversals now) use the initial elements, with access probability for any index (given uniform random leaf value lookups) decreasing as the depth increases.
(That is better than the rapidly varying pattern for binary searches in a linear array, as caches work in blocks larger than a typical element.)

Because of that, it is often useful to reorder data between linear and binary tree forms.

For at most $2^N-1$ elements, the element at linear array index $i$ is the same as index $k(i,N)$ in the binary tree array.
Equivalently, the element at index $k$ in the binary tree array is the same as the element at $i(k,N)$ in the linear array.
Thus, these two functions allow for easy mapping between the two orderings.

Before posting this, I have not seen methods that use direct index calculation for this reordering, only recursive or loop-based copy approaches. Direct index calculation allows the operation to be done in any order, which is important when researching for best cache behaviour. Now that Q the Platypus below identified the most important related sequences at The On-Line Encyclopedia of Integer Sequences, I can do a more comprehensive search. (Math is not my strongest field.)

Furthermore, $k(i,N)$ also answers the question "How do I access the $i$'th element in a binary search tree, stored as an array?", with between $2^{N-1}$ to $2^N-1$ elements, inclusive, in the tree. (The tree does not need to be perfect/full, it can also be almost complete; i.e. all levels full, except for the last, where all leftmost leaf elements are present, and one or more rightmost leaf elements not present.)

In real life implementations, binary trees are not the optimal solution for large amounts of data, especially if access patterns are not completely random, but consecutive accesses tend to cluster.
It seems that partitioned binary trees (or chunked binary trees, or nested binary trees) have even better cache behaviour. They are simply a binary tree of fixed-size binary subtrees, where each subtree consists of consecutive values.
The subtree size depends on the cache architecture used, and should be of form $2^n-1$ for perfect trees.
(For additions, leaf subtrees can be smaller to allow for relatively fast insertions without rebuilding the tree, although using a separate scoreboard for additions and deletions, that is merged to the actual tree when it grows large enough,
by rebuilding the tree completely, is sometimes a better approach. It's downside is the large occasional latency at accesses causing a rebuild.)

This is still heavily under research, as in applications not only the cache architecture, but also the individual element size varies.
However, the above $k(i,N)$ and $i(k,N)$ work for nested trees also (as the elements in the subtrees are always consecutive, and do not overlap with other subtrees). For selecting a particular subtree, just divide the indexes by the number of elements in each subtree.

Answer

I would write b as $$ b(x) = \begin{cases} x & x \nmid 2 \\ b(\frac{x}{2}) & x \mid 2 \end{cases} $$