Some interesting Usenet messages
List of articles
- 1a) sklam@cs.cuhk.hk (Ah kin): Re: [Pls Help] Question on shifting of bit
- Discussion of how to automate shifting bits outside of their integer
- 1b)scs@eskimo.com (Steve Summit): Re: Question on shifting of bit
- An example proglet to implement most of a straightforward algorithm
- 2) Jos A. Horsmeier: Re: Bitwise help??
- Some notes about doing multiplication with bits
From: sklam@cs.cuhk.hk (Ah kin)
Newsgroups: comp.lang.c
Subject: Re: [Pls Help] Question on shifting of bit
Date: 20 Jul 1996 02:31:10 GMT
Organization: Engineering Faculty CUHK
Message-ID: <4spgde$5n@eng_ser1.erg.cuhk.hk>
References: <4socju$gjt@eng_ser1.erg.cuhk.hk> <4soi8q$4p@news1.mnsinc.com>
Szu-Wen Huang (huang@mnsinc.com) wrote:
> Ah kin (sklam@cs.cuhk.hk) wrote:
> : I use the c-faq to define a array of bits.
> Bless you. :)
> : [quoted]
> : #define BITMASK(b) (1 << ((b) % CHAR_BIT))
> : #define BITSLOT(b) ((b) / CHAR_BIT)
> : #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
> : #define BITUNSET(a, b) ((a)[BITSLOT(b)] &= (char) 0)
> Did you write this yourself? The FAQ only has MASK, SLOT, SET, and
> TEST. It should be:
> ((a)[BITSLOT(b)] &= ~BITMASK(b))
> : #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
> : [quoted]
> : But how can I left/right shift the array of bits.
> Two methods, depending on your needs.
> 1. You may not need to physically shift the bit-array at all.
> You could just *remember* that the array was shifted 5 bits to
> the left. When you access the array, do arithmetic on the *index*
> then. For example, the old bit 10 is now bit 5, so instead
> of reading/writing to bit 10, you read/write to bit 5. You'll
> need to do range checks, though. For instance, BITTEST should
> then be:
> #define BITTEST(a, b) ((a)[BITSLOT(b+offset)] & BITMASK(b+offset))
> where offset is negative when the array is shifted left and
> positive when the array is shifted right.
> #define BITSHL(b) offset -= b;
> #define BITSHR(b) offset += b;
> ...
> static int offset = 0;
> Better yet, put the char array and int offset in a bit-string
> structure. Error checking et al left for your exercise. This
> may be all you need to do.
> 2. If you really need to shift the array physically, the trivial
> method is to:
> void shift_left(char *bit_array, int bit_array_size, int num_bits)
> {
> int i;
> /* copy every bit x to bit x-num_bits */
> for (i=num_bits; i<bit_array_size; i++)
> if (BITTEST(bit_array, i)
> BITSET(bit_array, i-num_bits);
> else
> BITUNSET(bit_array, i-num_bits);
> /* clear the last num_bits bits */
> for (i=bit_array_size-num_bits+1; i<bit_array_size; i++)
> BITUNSET(bit_array, i);
> }
> Again, error checking is left up to you. Faster implementations
> are possible, but more complicated, of course. Note that
> your loop should count from bit_array_size *down* to num_bits
> when shifting to the right.
> This solution is almost definitely slower than #1, of course.
Thank you for your help.
I need the method of physically shift the whole array of bits.
I have write the following code for your reference.
[quoted]
main()
{
char a[SLOT];
int i,j, shift;
char c, mask[CHAR_BIT];
int element;
/* Build the shift mask */
mask[0] = 1;
for(i=1;i<CHAR_BIT;i++) {
for(j=0;j<i;j++) mask[i] |= mask[j];
mask[i] |= 1 << i;
}
shift = 5; /* no. of bit to shift */
for(i=0;i<SLOT-1;i++){
/* Take the first n bit of the next slot */
c = mask[shift] & a[i+1];
c = c << (CHAR_BIT-shift);
/* shift the current slot and OR the above result */
(a[i]) = ((a[i]) >> shift) | c;
}
(a[i]) = ((a[i])>>1); /* for the last slot */
}
[quoted]
I wonder whether there is faster method in doing so?
yours,
Kin.
Newsgroups: comp.lang.c
From: scs@eskimo.com (Steve Summit)
Subject: Re: Question on shifting of bit
Message-ID: <Duy6Ar.C4q@eskimo.com>
References: <4soi8q$4p@news1.mnsinc.com>
<DuuMI6.KKM@eskimo.com> <4sromf$4n0@news1.mnsinc.com>
Date: Mon, 22 Jul 1996 13:47:14 GMT
In article <4sromf$4n0@news1.mnsinc.com>, huang@mnsinc.com
(Szu-Wen Huang) writes:
> Steve Summit (scs@eskimo.com) wrote:
> : The harder (but more efficient, if it matters) way is to shift
> : staggered chunks from one array element to the next. This is
> : obviously easier if the shift length is a multiple of the
> : element size (here, CHAR_BIT), harder if it's not.
> : I've... a sample piece of code... which begins to illustrate this.
>
> Actually I pondered about more efficient methods for a short while,
> then decided that keeping the carry in a temporary storage wouldn't
> be trivial if the number of bits to shift is greater than the size
> of the temporary carry variable. I'd be interested if you have a
> clever and efficient solution. Would your code work if we shift,
> say, 200 bits to the left?
Sure, although not all of you will probably think it's all that
clever, or even particularly efficient.
Here's a representation of the code I was talking about.
The array is of nwords elements, each holding BITSPERWORD bits.
The first piece of code shifts the bits n bits to the right.
ish is the number of *elements* to shift; it is obviously
n / BITSPERWORD. If BITSPERWORD divides n exactly, the code can
use the easy case, otherwise, it has to shuffle and recombine.
In the hard case, the temporary variables mask2 and new are
declared as having the same type (word_t) as the array elements.
int i, ish = n / BITSPERWORD;
if(n % BITSPERWORD == 0)
{
for(i = 0; i < nwords - ish; i++)
array[i] = array[i+ish];
}
else {
int shift1 = n % BITSPERWORD;
int shift2 = BITSPERWORD - shift1;
word_t mask2 = (1 << shift1) - 1;
for(i = 0; i < nwords - ish; i++)
{
word_t new = 0;
if(i + ish < nwords)
new |= array[i+ish] >> shift1;
if(i + ish + 1 < nwords)
new |= (array[i+ish+1] & mask2) << shift2;
array[i] = new;
}
}
/* now adjust nwords and/or zero out high-order bits */
Note that this code does *not* properly zero out the "high
order" elements of the array; the code I extracted it from was
adjusting nwords when it shifted, so it didn't have to.
The shift left case is similar; here we also need to know nbits,
the number of significant bits in the nwords words:
newnbits = nbits + n;
newnwords = (newnbits + BITSPERWORD - 1) / BITSPERWORD;
/* make sure array can hold newnwords words */
ish = n / BITSPERWORD;
if(n % BITSPERWORD == 0)
{
for(i = newnwords - 1; i >= 0; i--)
{
if(i - ish >= 0)
array[i] = array[i-ish];
else array[i] = 0;
}
}
else {
int shift1 = n % BITSPERWORD;
int shift2 = BITSPERWORD - shift1;
word_t mask1 = (1 << shift2) - 1;
for(i = newnwords - 1; i >= 0; i--)
{
word_t new = 0;
if(i - ish >= 0 && i - ish < nwords)
new |= (array[i-ish] & mask1) << shift1;
if(i - ish - 1 >= 0)
new |= array[i-ish-1] >> shift2;
array[i] = new;
}
}
These examples are from a multi-precision arithmetic package I
started throwing together one day. The obvious way to exercise
such a package is to wrap a calculator around it; here's the
calculator shifting a few numbers to the left. (It's a reverse-
Polish calculator, of course.)
? 1 200 << p
1606938044258990275541962092341162602522202993782792835301376
? 16 o # set output base to 16
? p
100000000000000000000000000000000000000000000000000
? 16 i # set input base to 16
? 123456789abcdef 9c << p
123456789abcdef000000000000000000000000000000000000000
? 0b4 >> p
123456789
So 2 ** 200 is 1,606,938,044,258,990,275,541,962,092,341,162,602,
522,202,993,782,792,835,301,376. (In our next episode, we'll
start raising large numbers to large powers modulo other large
numbers, and maybe violate U.S. Patent 4,405,829.)
Steve Summit
scs@eskimo.com
From: jos@and.nl (Jos A. Horsmeier)
Newsgroups: comp.lang.c
Subject: Re: Bitwise help??
Date: 27 Nov 1995 08:59:49 GMT
Message-ID: <49bum5$38l@beach.and.nl>
References: <49b7tu$kh0@news.tamu.edu>
In article <49b7tu$kh0@news.tamu.edu>, bdk9126@tam2000.tamu.edu wrote:
|>Hi I was wondering if someone could point me in the right direction
|>as to how to multiply two binary numbers without the "*" symbol or using
|>an addition loop. I know I can use the shift operator. For example:
[ example deleted ... ]
|>I see how the bits 1011 get shifted to the left in line 5 and then
|>the bits get added to give the result, But I am unfamiliar with the shift
|>operator and bitwise operations. If anyone feels they can help,
|>I would sincerly appreciate it.
The reason why you want to avoid the built-in multiplication operator
is beyond me, but nevertheless, here goes:
If a_n, a_n-1, ... a_1, a_0 represents a number a, then the product
of a and b is represented by:
a_n*(b * 2^n)+ a_n-1*(b * 2^n-1) + ... + a_0 * (b * 2^0)
( ^ denotes the exponentiation operator here ...)
Scanning this expression from right to left, we notice that the
parenthesized expressions e_i obey the following rules:
e_0 = b
e_i+1= 2* e_i
The last equation can be written as:
e_i+1 = e_i<<1
The factors a_i denote the i-th bit of a, so the factor c_i= a>>i
has its lowest bit equal to the i_th bit of the original factor.
Those two observations lead to something like this:
unsigned int mul(unsigned int a, unsigned int b) {
unsigned int result; /* sum of all e_i* c_i */
unsigned int e= b; /* e_0 == b */
unsigned int c= a; /* c_0 == a>>0 */
for (result= 0; c; c>>= 1, e<<= 1) { /* for all e_i and c_i */
if (c&1)
result+= e;
}
return result;
}
The two variables e and c are superfluous of course, i.e. we could have
performed the bit fiddling on variables b and a directly ...
I hope this clarifies things a bit,
kind regards,
Jos aka jos@and.nl
--
Atnwgqkrl gy zit vgksr, ug qshiqwtzoeqs!