Monday, July 12, 2004

 

Some C++ interview questions - 2

I.
发信人: granite (花岗岩), 信区: JobHunting
标 题: Goole phone interview questions
发信站: Unknown Space - 未名空间 (Wed Feb 9 15:14:16

2005)

1st round:
What are the public, private, protect in C++, what is

static.

private members of a class are accessible only from

other members of their same class or from their

"friend" classes.
protected members are accessible from members of their

same class and friend classes, and also from members of

their derived classes.
Finally, public members are accessible from anywhere

the class is visible.

Given a coordinate (x,y) of point A and millions of

coordinate of other points, find the first N points

closest to A. Give the algorithm and complexity.

priority queue, O(millions)

Given a string, count the occurrences of characters.

Hash Table

2nd round:
I only remember one question.
How to test if a BST is valid, in another word, has the

BST property.


/*
Returns true if the given tree is a binary search tree
(efficient version).
*/
int isBST2(struct node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
Returns true if the given tree is a BST and its
values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);

// false if this node violates the min/max constraint
if (node->datadata>max) return(false);

// otherwise check the subtrees recursively,
// tightening the min or max constraint
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}


发信人: granite (花岗岩), 信区: JobHunting
标 题: EMC interview questions
发信站: Unknown Space - 未名空间 (Wed Feb 9 15:24:26

2005)

How to let the variable in a C function keeps the value

last time it was assigned.

static

How to make the CPU finish its current work without

being interrupted?

blocking signal

In a system with multiple CPUs and a shared memory, how

to make them
communicate with each other without using locks.

spin lock

What are the ways to count number of 1s in an integer?

binary shift

发信人: granite (花岗岩), 信区: JobHunting
标 题: Paypal interview questions
发信站: Unknown Space - 未名空间 (Wed Feb 9 15:49:22

2005)

Phone
What’s static variable/function and protect in C++?
When to use exception when to use error code?
Two electrons move toward each other at 1m/s on a 10m

long line, they start at somewhere on the line. When

they meet, they change direction but keep the 1m/s

speed, what is the max time that there is no electron

on the line.
You are holding a stone on a boat in a pool, blah blah,

you know it …
Given a computer and a compiler, how to test the length

of the integer without using function like sizeof.

tricks on integer and char

On-site
I was showed a stupid recursive function to calculate

the length of a string.
Design a brute force solution to solve any word puzzle

(without using hint).
There are 10 columns of coins with each column contains

10 coins, one column has all it coins either heavier or

lighter than the coins in the rest of the columns by

1g, the coins in the other 9 columns are the same, how

to find the defected column by only measuring once? How

about 11 columns with 1 defected column, can you find

it? How about 12, can you find it?

10 column
pick 1 coin from the first column, 2 coins from the

second column, ..., pick 10 ten coins from the tenth

column, measure the total weight and done
11 column same
12 column, I just wonder whether there is a solution

of not.

Tell me about yourself, blah blah.
What ur previous manager would say about you, blah

blah.

Given a design:
Class connection {}:
Class application : public connection {};
What’s the problem can you see?

发信人: granite (花岗岩), 信区: JobHunting
标 题: Re: Paypal interview questions
发信站: Unknown Space - 未名空间 (Wed Feb 9 16:03:57

2005)

I said public inherit means "is a", but application

should "has a" connection.
The intewviewer is a junior engineer, he asked me for

some pratical answer not
OO answer. And he said this design didn't allow

application to share
connection which I doubted it.

This problem is really interesting, thanks for sharing

it

发信人: granite (花岗岩), 信区: JobHunting
标 题: Bloomberg phone interview questions
发信站: Unknown Space - 未名空间 (Wed Feb 9 15:54:33

2005)

What the compiler will write for you for a class Class

foo {};
How to prevent a class from created on stack? Heap?

tricks on construction function

Why copy constructor’s parameter is a reference but not

a object?

avoid create a new one

What’s placement new? How to delete object stored in

the memory by placement new?

Cool, this problem caught me. I nearly forgot it and

had to call Bjarne Stroustrup for help! ^_^


http://www.research.att.com/~bs/bs_faq2.html#placement-

delete
Thanks for sharing it

blah blah, all are very basic C++ stuff.

发信人: granite (花岗岩), 信区: JobHunting
标 题: Goldman Sach phone interview questions
发信站: Unknown Space - 未名空间 (Wed Feb 9 15:58:34

2005)

How to find loop in a linked list.
What’s the different between abstract factory and

factory method.
7 in base of 2 is 111, what is 7 in base of -2?

consider -7 on base of -2

Write a code snippets for basic BST operation like

insert, remove, search.

cslibrary.stanford.edu/110/BinaryTrees.html

祝大家鸡年大吉

Happy! Happy! Thanks for sharing those problems!

--
^C^

来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 65.96.

II.
发信人: goldhead (Family Man), 信区: JobHunting
标 题: C++ concept questions
发信站: Unknown Space - 未名空间 (Sun Feb 13 11:11:22 2005)

1) What you should do when a constructor fails?

2) What difficulties can you associate with multiple inheritance?

Any ideas?

--
--------
I am GoldHead and I approve this message.
http://www.oneimagehost.com/

[1m※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 69.81.]

Answer: 1)
From http://www.gotw.ca/publications/mill13.htm

Constructor Failures (or, The Objects That Never Were)
This article appeared in C/C++ Users Journal, 18(11), November 2000.

Function try blocks were added to C++ to slightly enlarge the scope of exceptions that a function can catch. This column will show:

o what object construction, and construction failure, mean in C++; and

o that function try blocks are useful to translate (not suppress) an exception thrown from a base or member subobject constructor -- and that's pretty much it.

For convenience, throughout this article "member" means "nonstatic class data member" unless otherwise noted.

Function Try Blocks
Consider the following class:

// Example 1
//
class C : private A
{
// ...

B b_;
};

In the C constructor, say you want to catch an exception thrown from the constructor of a base subobject (such as A) or a member object (such as b_). That's what function try blocks are for:

// Example 1(a): Constructor function try block
//
C::C()
try
: A ( /*...*/ ) // optional initialization list
, b_( /*...*/ )
{
}
catch( ... )
{
// We get here if either A::A() or B::B() throws.

// If A::A() succeeds and then B::B() throws, the
// language guarantees that A::~A() will be called
// to destroy the already-created A base subobject
// before control reaches this catch block.
}

The more interesting, question, though is: Why would you want to do this? That question brings us to the first of two key points in this column.

Object Lifetimes, and What a Constructor Exception Means
In a moment, we'll consider the question of whether the above C constructor can, or should, absorb an A or B constructor exception, and emit no exception at all. But before we can answer that question correctly, we need to make sure we fully understand object lifetimes[1] and what it means for a constructor to throw an exception.

Take a simple example:

{
Parrot parrot;
}

In the above code, when does the object's lifetime begin? When does it end? Outside the object's lifetime, what is the status of the object? Finally, what would it mean if the constructor threw an exception? Take a moment to think about these questions before reading on.

Let's take these items one at a time:

Q: When does an object's lifetime begin?

A: When its constructor completes successfully and returns normally. That is, when control reaches the end of the constructor body or an earlier return statement.

Q: When does an object's lifetime end?

A: When its destructor begins. That is, when control reaches the beginning of the destructor body.

Q: What is the state of the object after its lifetime has ended?

A: As a well-known software guru[2] once put it, speaking about a similar code fragment and anthropomorphically referring to the local object as a "he":

"He's not pining! He's passed on! This Parrot is no more! He has ceased to be! He's expired and gone to meet his maker! He's a stiff! Bereft of life, he rests in peace! If you hadn't nailed him to the perch he'd be pushing up the daisies! His metabolic processes are now history! He's off the twig! He's kicked the bucket, he's shuffled off his mortal coil, run down the curtain and joined the bleedin' choir invisible! This is an ex-Parrot!"

-- Dr. M. Python, BMath, MASc, PhD (CompSci)[3]

Kidding aside, the important point here is that the state of the object before its lifetime begins is exactly the same as after its lifetime ends -- there is no object, period. This observation brings us to the key question:

Q: What does emitting an exception from a constructor mean?

A: It means that construction has failed, the object never existed, its lifetime never began. Indeed, the only way to report the failure of construction -- that is, the inability to correctly build a functioning object of the given type -- is to throw an exception. (Yes, there is a now-obsolete programming convention that said, "if you get into trouble just set a status flag to 'bad' and let the caller check it via an IsOK() function." I'll comment on that presently.)

In biological terms, conception took place -- the constructor began --, but despite best efforts it was followed by a miscarriage -- the constructor never ran to term(ination).

Incidentally, this is why a destructor will never be called if the constructor didn't succeed -- there's nothing to destroy. "It cannot die, for it never lived." Note that this makes the phrase "an object whose constructor threw an exception" really an oxymoron. Such a thing is even less than an ex-object... it never lived, never was, never breathed its first. It is a non-object.

We might summarize the C++ constructor model as follows:

Either:

(a) The constructor returns normally by reaching its end or a return statement, and the object exists.

Or:

(b) The constructor exits by emitting an exception, and the object not only does not now exist, but never existed as an object.

There are no other possibilities. Armed with this information, we can now fairly easily tackle the question about absorbing exceptions.

I Can't Keep No Caught Exceptions[4]
In Example 1, if the A or B constructor throws an exception, is it possible for the C constructor to absorb the exception, and emit no exception at all? Well, if we didn't consider the object lifetime rules, we might have tried something like the following:

// Example 2(a): Absorbing exceptions?
//
C::C()
try
: A ( /*...*/ ) // optional initialization-list
, b_( /*...*/ )
{
}
catch( ... )
{
// ?
}

How will the try block handler exit? Consider:

o The handler cannot simply "return;" because that's illegal.

o If the handler says just "throw;" then it will rethrow whatever exception A::A() or B::B() originally emitted.

o If the handler throws some other exception, that exception is emitted instead of whatever the base or member subobject constructor originally threw.

o What's less obvious, but clearly stated in the C++ standard, is that if the handler does not exit by throwing an exception (either rethrowing the original exception, or throwing something new), and control reaches the end of the catch block of a constructor or destructor, then the original exception is automatically rethrown as if the handler's last statement had been "throw;".

Think about what this means: A constructor or destructor function try block's handler code must finish by emitting some exception. There's no other way. As long as you don't try to violate exception specifications, the language doesn't care what exception it is that gets emitted -- it can be the original one, or some other translated exception -- but an exception there must be! It is impossible to keep any exceptions thrown by base or member subobject constructors from causing some exception to leak beyond their containing constructors.

In fewer words, it means that:

In C++, if construction of any base or member subobject fails,
the whole objectmust fail.

This is no different from saying "there is no way for a human to exist (i.e., be born alive) if any of its vital organs (e.g., heart, liver) were never formed." If you tried to continue by keeping at least those parts you were able to make, the result may be a hunk of miscellaneous flesh -- an arm here, and ear there -- but it was never a human being. There is no such thing as an "optional" base or member (held by value or reference) subobject.

A constructor cannot possibly recover and do something sensible after one of its base or member subobjects' constructors throws. It cannot even put its own object into a "construction failed" state. Its object is not constructed, it never will be constructed no matter what Frankensteinian efforts the handler attempts in order to breathe life into the non-object, and whatever destruction can be done has already been done automatically by the language -- and that includes all base and member subobjects.

What if your class can honestly have a sensible "construction partially failed" state -- i.e., it really does have some "optional" members that aren't strictly required and the object can limp along without them, possibly with reduced functionality? Then use the Pimpl idiom (described in Exceptional C++ Items 27-30) to hold the possibly-bad parts of the object at arm's length.[5] For similar reasoning, see Exceptional C++ Items 31-34 about abuses of inheritance; incidentally, this "optional parts of an object" idea is another great reason to use delegation instead of inheritance whenever possible, because base subobjects can never be made optional because you can't put base subobjects into a Pimpl.[6]

I've always had a love/hate relationship with exceptions, and have sometimes taken a dim view of them. Even so, I've always had to agree that exceptions are the right way to signal constructor failures given that constructors cannot report errors via return codes (ditto for most operators). I have found the "if a constructor encounters an error, set a status bit and let the user call IsOK() to see if construction actually worked" method to be outdated, dangerous, tedious, and in no way better than throwing an exception.

A Step Toward Morality
Incidentally, this also means that the only (repeat only) possible use for a constructor function try block is to translate an exception thrown from a base or member subobject. That's Moral #1. Next, Moral #2 says that destructor function try blocks are entirely usele--

"--But wait!" I hear someone interrupting from the middle of the room. "I don't agree with Moral #1. I can think of another possible use for constructor function try blocks, namely to free resources allocated in the initializer list or in the constructor body!"

Sorry, no. After all, remember that once you get into your constructor try block's handler, any local variables in the constructor body are also already out of scope, and you are guaranteed that no base subobjects or member objects exist any more, period. You can't even refer to their names. Either the parts of your object were never constructed, or those that were constructed have already been destroyed. So you can't be cleaning up anything that relies on referring to a base or member of the class (and anyway, that's what the base and member destructors are for, right?).

Aside: Why Does C++ Do It That Way?
To see why it's good that C++ does it this way, let's put that restriction aside for the moment and imagine, just imagine, that C++ did let you mention member names in constructor try block handlers. Then imagine the following case, and try to decide: Should the handler delete t_ or z_? (Again, ignore for the moment that in real C++ it can't even refer to t_ or z_.)

// Example 2(b): Very Buggy Class
//
class X : Y
{
T* t_;
Z* z_;

public:
X()
try
: Y(1)
, t_( new T( static_cast(this) )
, z_( new Z( static_cast(this), t_ ) )
{
/*...*/
}
catch(...) // Y::Y or T::T or Z::Z or X::X's body has thrown
{
// Q: should I delete t_ or z_? (note: not legal C++)
}
};

The first problem is that we cannot possibly know whether t_ or z_ were ever allocated. Therefore deleting either one might not be safe.

Second, even if we did know that we had reached one of the allocations, we probably can't destroy *t_ or *z_ because they refer to a Y (and possibly a T) that no longer exists and they may try to use that Y (and possibly T). Incidentally, this means that not only can't we destroy *t_ or *z_, but they can never be destroyed by anyone.

If that didn't just sober you up, it should have. I have seen people write code similar in spirit to the above, never imagining that they were creating objects that, should the wrong things happen, could never be destroyed! The good news is that there's a simple way to avoid the problem: These difficulties would largely go away if the T* members were instead held by auto_ptrs or similar manager objects.

Finally, if Y::~Y() can throw, it is not possible to reliably create an X object at any time! If you haven't been sobered yet, this should definitely do it. If Y::~Y() can throw, even writing "X x;" is fraught with peril. This reinforces the dictum that destructors must never be allowed to emit an exception under any circumstances, and writing a destructor that could emit an exception is simply an error. Destruction and emitting exceptions don't mix.

All right, enough about that. The above side discussion was just to get a better understanding of why it's good that the rules are as they are. After all, in real C++ you can't even refer to t_ or z_ inside the handler in the first place. I've refrained from quoting standardese so far, so here's your dose... from the C++ standard, clause 15.3, paragraph 10: "Referring to any non-static member or base class of an object in the handler for a function try block of a constructor or destructor for that object results in undefined behavior."

Morals About Function Try Blocks
Therefore the status quo can be summarized as follows:

Moral #1: Constructor function try block handlers are only good for translating an exception thrown from a base or member subobject constructor (and maybe to do related logging or some other side effects in response to such failures). They are not useful for any other purpose.

Moral #2: Destructor function try blocks have little or no practical use, because destructors should never emit an exception.[7] Thus there should never be anything for a destructor function try block to detect that couldn't be detected with a normal try block -- and even if there were something to detect because of evil code (i.e., a member subobject whose destructor could throw), the handler would not be very useful for doing anything about it because it couldn't suppress the exception. The best it could do is would be to log something, or otherwise complain.

Moral #3: All other function try blocks have no practical use. A regular function try block can't catch anything that a regular try block within the function couldn't catch just as well.

Morals About Safe Coding
Moral #4: Always perform unmanaged resource acquisition in the constructor body, never in initializer lists. In other words, either use "resource acquisition is initialization" (thereby avoiding unmanaged resources entirely) or else perform the resource acquisition in the constructor body.

For example, building on Example 2(b), say T was char and t_ was a plain old char* that was new[]'d in the initializer-list; then there would be no way to delete[] it, in the handler or anywhere else. The fix would be to instead either wrap the dynamically allocated memory resource (e.g., change char* to string) or new[] it in the constructor body where it can be safely cleaned up using a local try block or otherwise.

Moral #5: Always clean up unmanaged resource acquisition in local try block handlers within the constructor or destructor body, never in constructor or destructor function try block handlers.

Moral #6: If a constructor has an exception specification, that exception specification must allow for the union of all possible exceptions that could be thrown by base and member subobjects. As Holmes might add, "It really must, you know." (Indeed, this is the way that the implicitly generated constructors are declared; see GotW #69.[8])

Moral #7: Use the Pimpl idiom to hold "optional parts" of a class If a constructor of a member object can throw but you can get along without said member, hold it by pointer and use the pointer's nullness to remember whether you've got one or not, as usual. Use the Pimpl idiom to group such "optional" members so you only have to allocate once.

And finally, one last moral that overlaps with the above but is worth restating in its own right:

Moral #7: Prefer using "resource acquisition is initialization" to manage resources. Really, really, really. It will save you more headaches than you can probably imagine, including hard-to-see ones like some we dissected above.

The Way It Is
The way the language works is entirely correct and easily defensible, once you think about the meaning of C++'s object lifetime model and philosophy.

A constructor exception must be propagated, for there is no other way to signal that the constructor failed. Two cases spring to mind:

// Example 2(c): Auto object
//
{
X x;
g( x ); // do something else
}

If X's construction fails -- whether it's due to X's own constructor body code, or due to some X base subobject or member object construction failure -- control must not continue within the scope of this code block. After all, there is no x object! The only way for control not to continue in f()'s body is to emit an exception. Therefore a failed construction of an auto object must result in some sort of exception, whether it be the same exception that caused the base or member subobject construction failure or some translated exception emitted from an X constructor function try block.

Similarly:

// Example 2(d): Array of objects
//
{
X ax[10];
// ...
}

Say the fifth X object construction fails -- whether it's due to X's own constructor body code failing, or due to some X base or member subobject construction failing. Then control must not continue within the scope of this code block. After all, if you tried to continue, you'd end up with a "holey array" -- an array not all of whose objects really exist. (Even that would probably be better than leaving things in a holy disarray, but I digress.)

A Final Word: Failure-Proof Constructors?
Is it possible to write and enforce an empty throw-specification for a constructor of a class (like C in Example 1), if some base or member constructor could throw? The answer is No; you could write the "I won't throw anything" empty throw-specification, but it would be a lie because there's no way to enforce it. After all, to enforce a "throws nothing" guarantee for any function, we must be able to absorb any possible exceptions that come our way from lower-level code, to avoid accidentally trying to emit them to our own caller. If you really want to write a constructor that promises not to throw, you can work around possibly-throwing member subobjects (e.g., if you can hold them by pointer or Pimpl because they truly are optional) but you can't work around possibly-throwing base subobjects -- another reason to avoid unnecessary inheritance, which always implies gratuitous coupling.

For a constructor to have an empty throw-specification, all base and member subobjects must be known to never throw, whether they have throw-specifications that say so or not. An empty throw-specification on a constructor declares to the world that construction cannot fail. If for whatever reason it can indeed fail, then the empty throw-specification is inappropriate.

What happens if you wrote an empty throw-specification on a constructor, and a base or member subobject constructor really does throw? The short answer: "Go to terminate(). Go directly to terminate(). Do not pass try, do not collect $200." The slightly longer answer: The function unexpected() gets called, which has two choices -- to throw or rethrow an exception allowed by the exception specification (impossible, since it's empty and won't allow anything) or to call terminate(). Then terminate(), in turn, immediately aborts the program.[9] In automobile terms: Screech, crunch.

Summary
A C++ object's lifetime begins only after its constructor completes successfully. Therefore throwing an exception from a constructor always means (and is the only way of reporting) that construction failed. There is no way to recover from failed construction of a base or member subobject, so if construction of any base or member subobject fails, the whole object's construction must fail.

Avoid function try blocks, not because they're evil but just because they offer few or no benefits over plain try blocks -- and when you're hiring you'll find that more people understand the latter than understand the former. This follows the principles of picking the simplest solution that's effective, and of writing for clarity first. Constructor function try blocks are useful only to translate exceptions emitted from base or member constructors, and all other function try blocks are rarely if ever useful at all.

Finally, as pointed out repeatedly in Items 8 to 19 of Exceptional C++, use owning objects and "resource acquisition is initialization" to manage resources, and you'll usually avoid having to write try and catch at all in your code, never mind in function try blocks.

Acknowledgments
Thanks to Bobby Schmidt for the questions and discussions that got me thinking about this topic.



Notes
1. For simplicity, I'm speaking only of the lifetime of an object of class type that has a constructor.

2. The inventor of the Python programming language?

3. The actual code example being commented upon by the above guru was only slightly different. Referring to the second Parrot object:

{
Parrot();
const Parrot& perch = Parrot();

// ... more code; at this point, only the first
// temporary object is pushing up daisies ...
}

Get it? It's a lifetime-of-temporaries-bound-to-references joke. Remember it for Bay area parties.

4. A double pun, can be sung to the chorus of "Satisfaction" or to the opening bars of "Another Brick in the Wall, Part N."

5. H. Sutter. Exceptional C++ (Addison-Wesley, 2000).

6. Convergence is funny sometimes. Long after I started pushing the Pimpl idiom and bashing needless inheritance, I kept on coming across new problems that were solved by using Pimpl or removing needless inheritance, especially to improve exception safety. I guess it shouldn't have been a surprise because it's just this whole coupling thing again: Higher coupling means greater exposure to failure in a related component. To this comment, Bobby Schmidt responded in private correspondence: "And maybe that's the core lesson to pull out of this -- we've really just rediscovered and amplified the old minimal-coupling-maximum-cohesion axiom."

7. Not even for logging or other side effects, because there shouldn't be any exceptions from base or member subobject destructors and therefore anything you could catch in a destructor function try block could be caught equally well using a normal try block inside the destructor body.

8. Available online at http://www.gotw.ca/gotw/069.htm.

9. You can use set_unexpected() and set_terminate() to get your own handlers invoked, which gives you a chance to do a bit of extra logging or cleanup, but then they'll end up doing much the same things.

III.
发信人: Phoenix (有凤来仪*Quiting BBS), 信区: Programming
标 题: Some interview questions.
发信站: The unknown SPACE (Wed Mar 8 11:51:41 2000)

I got some interesting interview questions to share with
you guys.
All C&C++ questions.
1) reversing a 8 bit binary number. like 11001111 ->11110011. No loop,
in space.
2) counting the number of 1 in an unsigned 8 bit. like how many 1s
in 10101100 ->4
3)
We had a block of code (a parser) that looked like this (simplified):
Where text is a pointer to a null terminated string, which may or may
not
be a tag name.
if ( strcmp( text, "
" ) == 0 )
{
... code ...
}
else if ( strcmp( text, "

" ) == 0 )
{
...code...
}
else if ( strcmp( text, "" ) == 0 )
{
...code..

Etc. It was a huge block of if/else cases. The code structure and
function
was something we were very happy with, so we didn't want to change the
code
inside the if cases. When we profiled it, however, the strcmp
functions
were consuming most of the program's execution time.

So my question is:
What could you do to make this more efficient without having to
rewrite the
code inside the if cases?

4)
We have a List and Vector class implemented as C++ templates. (Similar
to
the STL classes. But do to a porting restriction we couldn't use STL,
so we
wrote our own List & Vector.) We would like to add a Set class - a
class
that contains a group of objects, but where no object is duplicated.
Multiple adds of the same object do nothing.

Something like:
template
class Set
{
public:
void Add( const T& );
void Remove( const T& );
bool InSet( const T& );
};

So, given the existing classes, what is the best way to implement
this?
(You don't need to write the code, rather a brief description of how
it
might work.) What are the performance implications? Do you think it is
So, given the existing classes, what is the best way to implement
this?
(You don't need to write the code, rather a brief description of how
it
might work.) What are the performance implications? Do you think it is

better to use the List or Vector or implement the Set without them?

My solution to 3) and 4)
3) building a hash table and each string converted to a unique key,
but
writing string hash function is really cumbersome.
4) using a doubly link list and using array to index the link list.
Hashing
function may also be necessary.

Any suggestion is welcomed and wish you guys refresh me a lot.

--
去年我总是心太软,,今年我要该出手时就出手。

来源:.The unknown SPACE bbs.mit.edu.[FROM: 134.68.224.220]

For the first two problems, we can read the following code segments

http://www.elegant-software.com/software/aware/doc/html/
bits__n__bytes_8h-source.html

00001
00002 /*
00003 ** Copyright (C) 2002 Russell Leighton
00004 **
00005 ** This program is free software; you can redistribute it and/or modify
00006 ** it under the terms of the GNU General Public License as published by
00007 ** the Free Software Foundation; either version 2 of the License, or
00008 ** (at your option) any later version.
00009 **
00010 ** This program is distributed in the hope that it will be useful,
00011 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
00013 ** GNU General Public License for more details.
00014 **
00015 ** You should have received a copy of the GNU General Public License
00016 ** along with this program; if not, write to the Free Software
00017 ** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00018 */
00019
00020
00031 #ifndef __AW_BYTES__
00032 #define __AW_BYTES__
00033
00034 /* ############################ bytes ############################ */
00035 #define SWAPBYTES16(word) (00036 (((word)&0x00ff) << 8) | 00037 (((word)&0xff00) >> 8) 00038 )
00039
00040 #define SWAPBYTES32(word) (00041 (((word)&0x000000ff) << 24)| 00042 (((word)&0x0000ff00) << 8) | 00043 (((word)&0x00ff0000) >> 8) | 00044 (((word)&0xff000000) >> 24) 00045 )
00046
00047 /* non-zero if byteasword is in word, where byte is held to far right 8bits */
00048 #define BYTEINWORD32(word, byteasword)(00049 (((word)&0x000000ff) == (byteasword)) || 00050 ((((word)&0x0000ff00) >> 8) == (byteasword)) || 00051 ((((word)&0x00ff0000) >> 16) == (byteasword)) || 00052 ((((word)&0xff000000) >> 24) == (byteasword)) 00053 )
00054
00055 /* ############################ bits ############################ */
00056
00057
00058 /***********************************************************************00059 |macro: COUNTBITS16 |
00060 |purpose: count the bits that are 1 in a 16 bit lvalue |
00061 |usage: COUNTBITS16( bits ); |
00062 | or: count = COUNTBITS16( bits ); |
00063 |note: the lvalue argument always ends up with the result |
00064 \***********************************************************************/
00065 #define COUNTBITS16(b) (00066 (b)=(((b)>> 1)&0x5555)+((b)&0x5555),00067 (b)=(((b)>> 2)&0x3333)+((b)&0x3333),00068 (b)=(((b)>> 4)&0x0707)+((b)&0x0707),00069 (b)=(((b)>> 8)&0x000f)+((b)&0x000f),00070 (b))
00071
00072 /***********************************************************************00073 |macro: COUNTBITS32 |
00074 |purpose: count the bits that are 1 in a 32 bit lvalue |
00075 |usage: COUNTBITS32( bits ); |
00076 | or: count = COUNTBITS32( bits ); |
00077 |note: the lvalue argument always ends up with the result |
00078 \***********************************************************************/
00079 #define COUNTBITS32(b) (00080 (b)=(((b)>> 1)&0x55555555)+((b)&0x55555555),00081 (b)=(((b)>> 2)&0x33333333)+((b)&0x33333333),00082 (b)=(((b)>> 4)&0x07070707)+((b)&0x07070707),00083 (b)=(((b)>> 8)&0x000f000f)+((b)&0x000f000f),00084 (b)=(((b)>>16)&0x0000001f)+((b)&0x0000001f),00085 (b))
00086
00087 /***********************************************************************00088 |macro: COUNTBITS64 |
00089 |purpose: count the bits that are 1 in a 64 bit lvalue |
00090 |usage: COUNTBITS64( bits ); |
00091 | or: count = COUNTBITS64( bits ); |
00092 |note: the lvalue argument always ends up with the result |
00093 \***********************************************************************/
00094 #define COUNTBITS64(b) (00095 (b)=(((b)>> 1)&0x5555555555555555)+((b)&0x5555555555555555),00096 (b)=(((b)>> 2)&0x3333333333333333)+((b)&0x3333333333333333),00097 (b)=(((b)>> 4)&0x0707070707070707)+((b)&0x0707070707070707),00098 (b)=(((b)>> 8)&0x000f000f000f000f)+((b)&0x000f000f000f000f),00099 (b)=(((b)>>16)&0x0000001f0000001f)+((b)&0x0000001f0000001f),00100 (b)=(((b)>>32)&0x000000000000003f)+((b)&0x000000000000003f),00101 (b))
00102
00103 /***********************************************************************00104 |macro: REVERSEBITS16 |
00105 |purpose: reverse the bit order in a 16 bit lvalue |
00106 |usage: REVERSEBITS16( bits ); |
00107 | or: value = REVERSEBITS16( bits ); |
00108 |note: the lvalue argument always ends up with the result |
00109 \***********************************************************************/
00110 #define REVERSEBITS16(b) (00111 (b)=(((b)>> 1)&0x5555)|(((b)&0x5555)<< 1),00112 (b)=(((b)>> 2)&0x3333)|(((b)&0x3333)<< 2),00113 (b)=(((b)>> 4)&0x0f0f)|(((b)&0x0f0f)<< 4),00114 (b)=(((b)>> 8)&0x00ff)|(((b)&0x00ff)<< 8),00115 (b))
00116
00117 /***********************************************************************00118 |macro: REVERSEBITS32 |
00119 |purpose: reverse the bit order in a 32 bit lvalue |
00120 |usage: REVERSEBITS32( bits ); |
00121 | or: value = REVERSEBITS32( bits ); |
00122 |note: the lvalue argument always ends up with the result |
00123 \***********************************************************************/
00124 #define REVERSEBITS32(b) (00125 (b)=(((b)>> 1)&0x55555555)|(((b)&0x55555555)<< 1),00126 (b)=(((b)>> 2)&0x33333333)|(((b)&0x33333333)<< 2),00127 (b)=(((b)>> 4)&0x0f0f0f0f)|(((b)&0x0f0f0f0f)<< 4),00128 (b)=(((b)>> 8)&0x00ff00ff)|(((b)&0x00ff00ff)<< 8),00129 (b)=(((b)>>16)&0x0000ffff)|(((b)&0x0000ffff)<<16),00130 (b))
00131
00132 /***********************************************************************00133 |macro: REVERSEBITS64 |
00134 |purpose: reverse the bit order in a 64 bit lvalue |
00135 |usage: REVERSEBITS64( bits ); |
00136 | or: value = REVERSEBITS64( bits ); |
00137 |note: the lvalue argument always ends up with the result |
00138 \***********************************************************************/
00139 #define REVERSEBITS64(b) (00140 (b)=(((b)>> 1)&0x5555555555555555)|(((b)&0x5555555555555555)<< 1),00141 (b)=(((b)>> 2)&0x3333333333333333)|(((b)&0x3333333333333333)<< 2),00142 (b)=(((b)>> 4)&0x0f0f0f0f0f0f0f0f)|(((b)&0x0f0f0f0f0f0f0f0f)<< 4),00143 (b)=(((b)>> 8)&0x00ff00ff00ff00ff)|(((b)&0x00ff00ff00ff00ff)<< 8),00144 (b)=(((b)>>16)&0x0000ffff0000ffff)|(((b)&0x0000ffff0000ffff)<<16),00145 (b)=(((b)>>32)&0x00000000ffffffff)|(((b)&0x00000000ffffffff)<<32),00146 (b))
00147
00148 #endif




<< Home

This page is powered by Blogger. Isn't yours?