7

Looking at the int 44 — I need Math.CEIL (log(2) 44) of binary places to represent 44. (answer is 6 places)

6 places : 

___  ___  ___  ___  ___   ___
32   16    8    4    2     1

But how can I check that (for example) the bit of 8 is checked or not ?

A simple solution will be do to :

((1<<3) & 44)>0 so this will check if the bit is set.

But please notice that behind the scenes the computer translates 44 to its binary representation and just check if bit is set via bitwise operation.

Another solution is just to build the binary myself via toString(2) or mod%2 in a loop

Question

Mathematically Via which formula, I can test if n'th bit is set ?

(I would prefer a non loop operation but pure single math phrase)

Royi Namir
  • 144,742
  • 138
  • 468
  • 792
  • 5
    *Mathematically*, there are no spoons - erm, I mean bits. – Jongware Jul 06 '15 at 08:46
  • 1
    @RoyiNamir, but what wrong with bitwise operation? why you want avoid it? – Grundy Jul 06 '15 at 08:54
  • :) But still – "the computer translates 44 to its binary representation and just check if bit is set via bitwise operation", no, that is mixing metaphors (or maybe just techniques). "The n'th bit" **is** a bitwise operation. This is the same as checking the value of "the n'th decimal" in a large decimal number (and for any other base). I'm pretty sure you'll need something like a mod and a div somewhere. – Jongware Jul 06 '15 at 08:55
  • Any hint *why* you don't want binary operations? This is the most efficient way of operating on bits (way more efficient than `toString` or `%`). Alternately, you can use `log`, as you obviously know. – Amadan Jul 06 '15 at 08:56
  • @Amadan I'm building a tinyURL like generator so I have `abc..ABC...0..9` which is 26+26+10 which is 62 options so it's base 62. now , after I have the number to encode (44) and I have the number of places . but now iterating through each place I need to knowif there's vlue and what is the value – Royi Namir Jul 06 '15 at 09:01
  • @RoyiNamir, you have a fixed number set? like from 1 to 100? – Grundy Jul 06 '15 at 09:07
  • Instead of 2 options in base 2 I have 62 options . – Royi Namir Jul 06 '15 at 09:08

3 Answers3

8

Divide by the value of the bit that you want to check and test if the first bit is set (this can be tested with x mod 2 == 1)

Math expression:

floor(value/(2^bitPos)) mod 2 = 1

As JS function:

function isSet(value, bitPos) {
   var result =   Math.floor(value / Math.pow(2, bitPos)) % 2;
   return result == 1;
}

Note: bitPos starts with 0 (bit representing the nr 1)

davidgiga1993
  • 2,695
  • 18
  • 30
6

The 'bit' (actually any base) value of an indexed number index in a value val in base base can in general be calculated as

val = 1966;
index = 2;
base = 10;
alert (Math.floor(val/Math.pow(base,index)) % base);

result: 9

val = 44;
index = 3;
base = 2;
alert (Math.floor(val/Math.pow(base,index)) % base);

result: 1 (only 0 and 1 are possible here – the range will always be 0..base-1).

The combination of Math.floor (to coerce to an integer in Javascript) and Math.pow is kind of iffy here. Even in integer range, Math.pow may generate a floating point number slightly below the expected 'whole' number. Perhaps it is safer to always add a small constant:

alert (Math.floor(0.1+val/Math.pow(base,index)) % base);
Jongware
  • 22,200
  • 8
  • 54
  • 100
  • In what scenarios would 0.1 help ? can you supply example ? – Royi Namir Jul 06 '15 at 10:46
  • Read [Understanding floating point problems](http://stackoverflow.com/q/4664662/2564301) (and [What Every Computer Scientist Should Know About Floating-Point Arithmetic](http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html), mentioned in one of the answers). Javascript doesn't "do" real integers. Also, `Math.pow` is a pure floating point operation, and as such it *may* be inaccurate. (I just tested for some random ranges and didn't find an example–still, it may depend on the JS engine.) – Jongware Jul 06 '15 at 10:56
  • 1
    Read it many times to mention. But I was hoping that you supply an example that will support that `0.1` floor helper. – Royi Namir Jul 06 '15 at 11:01
  • @Royi: sorry, I just tested `1..35` for both base and exponent - found not one! :) But [the specification](http://www.ecma-international.org/ecma-262/6.0/#sec-math.pow) is vague on this: "... an implementation-dependent approximation ..." The idea of using `0.1`, by the way, is that the epsilon is somewhere in the order of 10⁻⁴. See for example [C's pow() function as per header file not working properly](http://stackoverflow.com/q/3509423/2564301) for C. – Jongware Jul 06 '15 at 11:49
1

You can simply check if the bit at the position is set to 1.

function isBitSet(no, index) {
    var bin = no.toString(2);
    // Convert to Binary

    index = bin.length - index;
    // Reverse the index, start from right to left

    return bin[index] == 1;
}
isBitSet(44, 2); // Check if second bit is set from left

DEMO

Tushar
  • 85,780
  • 21
  • 159
  • 179