17
$\begingroup$

For a number $x$, I would like to know whether there is a common name for the number $2^n$ such as $2^n \leq x < 2^{n+1}$ (e.g. If $x = 7$, then $2^n = 4$, $n = 2$).

I have some computer science related article where I extensively use such a number and I need a name to give it in order to explain how an algorithm works without having to repeat the number definition over and over every time I need to use it. I currently call it a "base $2$", saying for example that "$4$ is the base $2$ of $7$" (see example above), and that we need to "compute the base $2$ of the number", but this name feels wrong. Do you know whether a common name exists for such a number?

Note: actually, the article I am talking about deals with Gray codes. I am looking for a term that looks like it comes from math and not from computer science since many terms from computer science that deal with powers of two tend to be references to the usual binary representations of numbers. As an example, with Gray codes $2^3$ is 0b1100 and not 0b1000 so I am trying to avoid names that would literally mean the $n$th set bit, hence the question on Math.SE.

Note 2: as it has been highlighted in the many answers and comments, the goal of this question, once clearly reformulated, is to find a terse, pronounceable name for the function $2^{\lfloor \log_2(x) \rfloor}$ so that it is possible to say that "some number is the [insert name here] of $x$".

$\endgroup$
13
  • 4
    $\begingroup$ For what it's worth, octave and binade? They are used to describe ranges rather than a specific value, but you could say that the value is the octave's or binade's base. Let u define the octave of an integer N as the set of numbers [2^n, 2^n+1) that contains N, and the base of an octave as the lowest integer contained in that set... $\endgroup$ Jun 3 '15 at 11:24
  • 2
    $\begingroup$ @IwillnotexistIdonotexist I like the term octave and find it clear, but it may be because of my musical background more than because of my computer science background :) $\endgroup$
    – Morwenn
    Jun 3 '15 at 11:52
  • 3
    $\begingroup$ call it the two-power of x. You can easily modify that for other numbers then as well $\endgroup$
    – snulty
    Jun 3 '15 at 12:00
  • 2
    $\begingroup$ What about flog (and ceilog) ? $\endgroup$
    – user65203
    Jun 3 '15 at 19:26
  • 2
    $\begingroup$ Here's a question stated differently, but in terms of content inherently the same: math.stackexchange.com/questions/1292951/… $\endgroup$
    – user90667
    Jun 3 '15 at 19:55

14 Answers 14

19
$\begingroup$

In the context of data structures - specifically, the van Emde Boas layout - I've heard this referred to as the hyperfloor of $x$. See “Cache-Oblivious B-Trees (Wayback Machine) by Bender, Demaine, and Farach-Colton for details - it defines the hyperfloor of $x$, denoted $\lfloor \lfloor x \rfloor \rfloor$, to be $2^{\lfloor \log_2 x \rfloor}$.

Hope this helps!

$\endgroup$
3
  • $\begingroup$ As much as I like the binadic floor proposal, it seems that the name hyperfloor is indeed used to represent this function (and hyperceiling to represent the the upper bound of the binade). I think that it's the term that I will use from now on. Thanks again :) $\endgroup$
    – Morwenn
    Jun 4 '15 at 7:59
  • $\begingroup$ On a side note, I guess that the internet needs to be updated so that searching for hyperfloor in our favourite search engine returns an accurate definition of the function. $\endgroup$
    – Morwenn
    Jun 4 '15 at 8:19
  • $\begingroup$ Also, I've seen flp2 as the function name (standing for "floor to the next power of 2"). $\endgroup$
    – user541686
    Jun 4 '15 at 8:37
13
$\begingroup$

If $x$ is an integer, then $n+1$ is the bit length of $x$.

$\endgroup$
7
  • $\begingroup$ Well, I would like to find a name that reminds of maths and not of computing. Actually, I'm dealing with Gray code where $2^4$ is 0b1100 for example so names that were chosen for computer science with regular binary representation in mind can be can misleading. I reckon that it wasn't clear from the question though, I will add a note. $\endgroup$
    – Morwenn
    Jun 3 '15 at 9:14
  • 2
    $\begingroup$ @Morwenn: "Bit length" works perfectly fine with Gray codes, what makes you think it doesn't? The wikipedia article even uses the equivalent term "bit width" at the top of the page. $\endgroup$ Jun 3 '15 at 20:09
  • 7
    $\begingroup$ I don't understand. The question explicitly asks for a name for $2^{\lfloor \log_2 x\rfloor}$, not for $\lfloor \log_2 x\rfloor+1$. $\endgroup$ Jun 3 '15 at 21:06
  • 3
    $\begingroup$ I don't understand why a high-rep user is posting something that manifestly doesn't answer the question, and getting a bunch of upvotes for it. Or are you implicitly answering "two to the bit-length-minus-1"? $\endgroup$ Jun 3 '15 at 22:42
  • 3
    $\begingroup$ @DavidRicherby: That's three questions! To answer them in order: (i) I posted it because I thought it might help. (ii) I have no idea why I got a bunch of upvotes. (iii) Yes. $\endgroup$
    – TonyK
    Jun 3 '15 at 23:02
9
$\begingroup$

You could call it $2^{\lfloor \log_2(x) \rfloor}$.

$\endgroup$
7
  • 4
    $\begingroup$ And how is it pronounced? ;-) $\endgroup$ Jun 3 '15 at 10:57
  • 21
    $\begingroup$ It's pronounced Frederick $\endgroup$
    – snulty
    Jun 3 '15 at 11:58
  • 3
    $\begingroup$ Since this function is well defined for all the numbers you are treating, you could simply introduce the function $\mathbb{R}\rightarrow 2^{\mathbb{N}}$ $\text{Fred}(x)=2^{[\log_2(x)]}$ and recall it in this way. $\endgroup$
    – Lonidard
    Jun 3 '15 at 23:03
  • 5
    $\begingroup$ "Two to the Power of the Floor of the Base-Two Logarithm" = TPFBTL of x, pronounced kinda like "top of bottle". $\endgroup$
    – Dan
    Jun 4 '15 at 0:22
  • 4
    $\begingroup$ I am really in favor of introducing the name 'top of bottle' for this! It is clear that this function is useful in more (mostly CS-related) situation and top of bottle is an easy to remember name that also relates directly to the proper description of this function. I say we all start plugging in into casual conversation over the next weeks! Thanks Dan for coming up with it! $\endgroup$
    – Vincent
    Jun 4 '15 at 7:45
8
$\begingroup$

Moved from comment

I suggest derivations from octave or binade. These words are typically used to describe ranges spanning powers of two rather than a specific value within them, but because a power-of-two uniquely defines an octave/binade (it is its lowest value; in other words, it is a base value, or a floor), you could use the same word for both the interval and this defining value.

For instance, you could name it the binadic floor. I favour this expression because the concept of binades is clear once formulated, and the concept of floor is unambiguous and generally well-understood. The rarity of "binade" means that "binadic floor" is sufficiently unusual as to not be confused with the regular floor, and "binadic floor" rolls quite well off the tongue.

Another possibility is octaval base/root/floor, but "octave", "base" and "root" all have pre-existing connotations, and when spoken, octaval floor doesn't sound right because the -al and fl- interact poorly, forcing a break.

Let us define the binade of a positive integer $N$ as the set of integers $[2^n, 2^{n+1})$ that contains $N$, and the binadic floor of an integer $N$ as the lower bound of $N$'s binade...

$\endgroup$
5
  • 4
    $\begingroup$ After reading the (draft) Wikipedia article, binade seems quite excellent. We would just have to tweak the definition to make it more general, with open and closed binades to make it clear that we're not including the upper bound. Also, while it applies to floating point numbers, I don't see why it couldn't be expanded to arbitrary numbers. Seems like a good fit. Introducing the floor and ceil of a binade could be meaningful in our case :) $\endgroup$
    – Morwenn
    Jun 3 '15 at 15:33
  • $\begingroup$ @Morwenn And, if you ever need it, you can talk of trinades, quadranades, 5-nades… (or pentanades, but you have to stop with the Latin somewhere). $\endgroup$ Jun 3 '15 at 19:22
  • $\begingroup$ @Morwenn Actually, binade already implies closed-at-bottom, open-at-top intervals; The reason being that all values in such an interval share the same IEEE-754 exponent. A power of two is the lowest-valued floating-point number to have any given exponent in IEEE-754 representation. $\endgroup$ Jun 3 '15 at 19:27
  • $\begingroup$ @Morwenn I've brooded on this topic for some more time and settled on a name I like a lot, and edited it in above: binadic floor. $\endgroup$ Jun 4 '15 at 2:23
  • 1
    $\begingroup$ I definitely like the proposed name, but @templatetypedef found the equivalent hyperfloor which seems to already be used in some research papers and sparsely around the web. As much as I like binadic floor, I will go with hyperfloor for consistency :/ $\endgroup$
    – Morwenn
    Jun 4 '15 at 8:01
4
$\begingroup$

I would just describe it as the "largest power of two not exceeding $x$". See A053644 in OEIS for other names and information.

$\endgroup$
1
  • 2
    $\begingroup$ That seems to be my OEIS entry, where I called it the most significant bit of $n$. $\endgroup$
    – Henry
    Jun 4 '15 at 12:35
3
$\begingroup$

I don't know a standard term, but "dyad" might be a good choice. The word roughly means "twoness", and is used for example in dyadic decompositions in a manner similar to the one you want.

A less exotic name would be "order of magnitude". (Explaining that it is with respect to base $2$.)

$\endgroup$
2
  • 3
    $\begingroup$ While it sounds cool (I really mean it), almost everywhere I checked, it was more used to represent a pair of things :/ $\endgroup$
    – Morwenn
    Jun 3 '15 at 11:54
  • 4
    $\begingroup$ Order of magnitude is spot on, but you do need to be clear that's is base-two, because almost evey body will interpret it as base 10. $\endgroup$ Jun 3 '15 at 15:21
3
$\begingroup$

The term I have always been using for that number is x rounded down to a power of two. I can't imagine a term which would be shorter to pronounce. The shortest symbolic notation suggested in other answers, would be pronounced as two raised to the log base two of x rounded down, which is a bit longer to pronounce and harder to understand when you hear it said.

$\endgroup$
1
  • 5
    $\begingroup$ Even shorter (but perhaps less clear): power of 2 below, would only use this in speech, not in a definition: 'Here we have 16, the power of 2 below 18'. You may want to include 'greatest' and if you are talking about 16, just state that it is a power of 2. $\endgroup$ Jun 3 '15 at 16:11
1
$\begingroup$

Why not something like "binary downscale", since you're basically treating the powers of two as a scale for rounding down. It's not all too descriptive, but it sounds like you want something short.

When using it, you could say "14's binary downscale is 8".

$\endgroup$
0
1
$\begingroup$

I might call it the "logarithmic floor", although this term is not well known (I just coined it), It could perhaps be misinterpreted to mean $e^{\lfloor \ln x \rfloor}$ or $10^{\lfloor \log_{10} x \rfloor}$, but in the context of Gray codes I'd think base-2 would be semi-implied.

$\endgroup$
2
  • $\begingroup$ I think "exponential floor" would make more sense (since you always end up with something like $2^n$), but that's just me. $\endgroup$ Jun 3 '15 at 19:26
  • $\begingroup$ @columbus8myhw, nice point. Maybe "binary floor" is good enough in this case. $\endgroup$ Jun 3 '15 at 19:36
0
$\begingroup$

You're after the arithmetic value of the most significant digit of the number, when written in binary. As a digit it is always 1, of course (unless the number is zero), but if you're inventing terminology you can say "the most significant (binary) digit of 7 has value 4", and kind of make sense.

$\endgroup$
2
  • 2
    $\begingroup$ Wouldn't it make more sense to say "the most significant bit"? "Bit" being short for "binary digit". $\endgroup$ Jun 3 '15 at 19:24
  • $\begingroup$ It would in a programming context, but in mathematics we used to just talk about digits regardless of base. E.g., Cantor's diagonalization proof is about binary digits, not bits. $\endgroup$
    – alexis
    Jun 3 '15 at 19:53
-1
$\begingroup$

You could maybe use the fact that the upper end-point is twice as large as the lower end-point. Something like even interval or double interval ..

$\endgroup$
-1
$\begingroup$

I think it is called Binary logarithm. Wikipedia page:

http://en.wikipedia.org/wiki/Binary_logarithm

$\endgroup$
3
  • 2
    $\begingroup$ As you can see from @cxseven's answer, I'm looking for a cool name for $2^{\lfloor \log_2(x) \rfloor}$, not for $\log_2(x)$. $\endgroup$
    – Morwenn
    Jun 3 '15 at 14:40
  • 1
    $\begingroup$ @Morwenn If you want it to be short and simple to read, why not "Let $f(x) = 2^{\lfloor\log_2 (x)\rfloor}$. Then we have $f(7)=4$"? $\endgroup$
    – user12205
    Jun 3 '15 at 21:04
  • $\begingroup$ @ace That's what I would have done if there wasn't already a recognized terse name for the function :) $\endgroup$
    – Morwenn
    Jun 4 '15 at 9:06
-1
$\begingroup$

It seems like your n + 1 is the most significant bit, so maybe a good name would be the second most significant bit, or maybe the almost significant bit?

$\endgroup$
1
  • 1
    $\begingroup$ isn't the first bit most significant though? $\endgroup$
    – Cruncher
    Jun 3 '15 at 20:29
-1
$\begingroup$

How about truncate? That is, you truncate all but the most significant digit to 0.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.