Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an arbitrary number $n$, what's the best way to set every $k^{th}$ bit to zero?

For example, given $354_{10}$=$101101010_2$, setting every 3rd bit counting from the right to zero would give me $66_{10}$=$001001010_2$.

I'm looking for a technique similar to the following for setting the leading bits to zero: If for instance I wanted to set the leading four bits to zero, I would calculate the desired answer $n'$ as

$$n_0=2^4 n \text{ } (\text{mod } 2^9)$$ $$n'=n_0/2^4$$

Of course, this question should generalize for numbers of different bases.

share|improve this question

3 Answers 3

What you seem to be asking for is a way to express this operation in conventional mathematical notation. But conventional mathematical notation doesn't have standard symbols for bitwise operations. This isn't because those operations are somehow illegitimate, or because the conventional notation is somehow better. It's just because those operations were studied later than the other ones and are less entrenched in history. Where the conventional notation does provide a simple expression of a bit operation, as in your example, that is a coincidence.

So it's a bit of a puzzle what you are really looking for. If you need a way to express these operations compactly, you can make up your own compact notation, or you can look at the notation used by computer programming languages, which have solved this problem before, and the conventional notation is unlikely to make anything clearer. If you need an efficient algorithm to calculate the result of this operation, that is a different question, again unrelated to conventional mathematical notation. But the thing you seem to be asking for, a concise expression of this operation in standard number-theoretic symbols, I believe does not exist.

share|improve this answer
    
I was looking for a concise expression of the operation in standard number-theoretic symbols; I'm still hoping that it exists! –  Vincent Tjeng Mar 9 at 22:41
    
@VincentTjeng Do you have a particular motivation for wanting this in standard number-theoretic terms? Or just hoping for purely aesthetic reasons? –  Erick Wong Mar 11 at 5:24
    
I didn't know about enough about bitwise operators to realize that they could be used here; furthermore, I was writing a proof where I required this operation, and I thought that expressing this in standard number-theoretic terms would be clearer for the reader, since my proof is targeted at people without a computer programming background. (Aesthetically, it would also be great too.) –  Vincent Tjeng Mar 11 at 16:28

One representation I can think of is with bitwise AND is $n \ \& \dots011011011011$. This is essentially a bitmask. There's also the double nested symbol mentioned here but I've never seen it before.

share|improve this answer

Not sure why you would want to do this, but here's a straightforward way.

Input: a base $b$, an integer $a = \sum_{i = 0}^n a_ib^i$, $a_n \ne 0$, and an integer $k \le n$.
Output: The integer $a' = \sum_{i \ne k} a_ib^i$, i.e., $a$ with $a_k$ set to $0$.

  1. Set $A \gets a \mod{b^{k+1}}$.
  2. Set $B \gets A - (A \mod{b^k})$.
  3. Output $a-B$.

Repeat as needed to set several digits to $0$.

EDIT (after fix): So the result can be expressed as $a - (a \mod {b^{k+1}}) + (a \mod {b^k})$.

share|improve this answer
    
Hey there, doesn't this set $a_i$ to 0 for all $i>k$? I don't see how it maintains the information needed. –  Vincent Tjeng Mar 11 at 2:53
    
Sorry, I was thinking in binary... Fixed. –  fkraiem Mar 11 at 4:08
    
Thanks! I was slightly confused by the initial solution :) –  Vincent Tjeng Mar 11 at 16:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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