Blogs
Linked List: Detect a Cycle in a linked list and Fix the cycle
Thu, 10/20/2005 - 03:29 — tekpoolQ: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
In the Previous posts, we discussed several ways to find cycles in a list, starting from some O (n^2) trival solutions, to the classic Flyod's Cycle Finding Algorithm (also known as the Hare and Tortoise approach, or the 2 pointer approach) and a asymptotic faster variant, to a list reversal technique (which I havent seen being used anywhere). There are a few O(n lg n) solutions which I did not mentoin here. (If there is enought interest I will post this).
Linked List: Detect a Cycle in a linked list - List Reversal
Thu, 10/06/2005 - 15:40 — tekpoolQ: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a few soIutions prior to this. Lets look into an easy but not so commonly used solution.
Sol 5: Find Cycle through List Reversal
We've looked into some classic approaches of Linked List Cycle Finding Methods (Hare and Tortoise) in the previous posts. Lets see a more easier straightforward approach. I am a bit surprised this is not a usually used method.
Linked List: Detect a Cycle in a linked list - Two Pointers Approach (Faster)
Wed, 10/05/2005 - 15:25 — tekpoolQ: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions
Sol 4: Two pointer approach (Faster)
In the last post we discussed about the regular two pointer approach and a bit about its background. Lets look into how we can make it a bit faster.
Linked List: Detect a Cycle in a linked list - Two Pointers Approach (Slow)
Mon, 10/03/2005 - 02:27 — tekpoolQ: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions
Sol 3: Two pointer approach (Slow)
Linked List: Detect a Cycle in a linked list - Trival Approaches
Thu, 09/29/2005 - 05:24 — tekpoolQ: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
I will use the following code use in all (single) linked list programs:
struct LNode {
int data;
LNode* next;
LNode() {
next=NULL;
}
};
class LinkedList {
LNode* head;
}
For the sake of simplicity, I have put only an int field 'data' in the LNode struct. The LinkedList class currently only has a head pointer. I will add functions to it as we go along.
Bit Count: Parallel Counting - MIT HAKMEM
Wed, 09/28/2005 - 07:22 — tekpoolQ: Find the number of set bits in a given integer
Sol: Parallel Counting: MIT HAKMEM Count
HAKMEM (Hacks Memo) is a legendary collection of neat mathematical and programming hacks contributed mostly by people at MIT and some elsewhere. This source is from the MIT AI LABS and this brilliant piece of code orginally in assembly was probably conceived in the late 70's.
int BitCount(unsigned int u)
{
unsigned int uCount;
uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return Bit Count: Unset Bit Iterator
Wed, 09/28/2005 - 07:17 — tekpoolQ: Find the number of set bits in a given integer
Sol: Unset Bit (0's) Iterator
This is similar to the Set Bit Iterator method, expect that all bits are toggled before iteration, and uCount is decremented whenever a set bit (originally unset) is encountered.
int BitCount (unsigned int u)
{
//number of bits in unsigned int
unsigned int uCount= 8 * sizeof(unsigned int);
// Toggle bits
u ~= (unsigned int) -1 ;
for(; u; u&=(u-1))
uCount--;
return uCount ;
}
Bit Count: Set Bit Iterator
Wed, 09/28/2005 - 07:14 — tekpoolQ: Find the number of set bits in a given integer
Sol: Set Bit (1's) Iterator
Here, the line u &= u-1 flips the highest set bit in each iteration, until there are no more set bits.
int BitCount (unsigned int u)
{
unsigned int uCount=0 ;
for(; u; u&=(u-1))
uCount++;
return uCount ;
}
Running time is proportional to the number set bits, Useful when there are less number of set bits in the number
Bit Count: Looping through the Bits
Wed, 09/28/2005 - 07:05 — tekpoolQ: Find the number of set bits in a given integer
Sol: Looping through all the bits
In this approach, the number is looped through all its bits one by one using a right shift, and checking if the low bit is set, in every iteration by AND’ing with 0x1u
int BitCount(unsigned int u)
{
unsigned int uCount = 0;
for(; u; u>>=1)
uCount += u & 0x1u;
return uCount;
}
Bit Count: Pre-Computing Bits
Tue, 09/27/2005 - 04:46 — tekpoolQ: Find the number of set bits in a given integer?
Sol: Pre-Computing Bits
static unsigned int NumBits8Bit[256] ;
//Precompute this array of size 256, each element in the array denoting the number of bits in a char (0x00 to 0xff). Then separate divide the number of interest into 4 blocks of 8 bits each by masking the last 8 bits (ANDing it with 0xffU) and right shifting by 8 bits each time. Sum up the count and return
int BitCount (unsigned int u)
{
return NumBits8Bit [u & 0xffU]
